Asymptotic expected runtime of Randomized Algorithm
As you mention, it is easy to prove by induction that the overall runtime is $O(n^2)$. If we don't have any more information, that's (almost) all we can deduce. For example, suppose that at each instance we pay a cost of $O(1)$. The running time will then be $O(n)$. In order to make progress, we have to assume that at each instance we pay a cost of $\Theta(n)$. In that case, we can argue as follows:


Since each "jump" is $O(1)$, it takes $\Omega(n)$ steps (on average) to reach $n/2$.
At each of these $\Omega(n)$ steps, we pay a cost of $\Omega(n)$.
Hence the total expected cost is $\Omega(n^2)$.


This is not a rigorous argument, but it can be turned into one if you're careful enough.