3
$\begingroup$

I am analyzing the asymptotic runtime of a randomized algorithm in expectation. The algorithm has the following properties:

  • Given input size $n$, with probability $3/4$ it moves on to solve an instance of size $n-1$
  • With probability $1/8$ it moves on to solve an instance of size $n-2$
  • With probability $1/16$ it moves on to solve an instance of size $n-3$
  • With probability $1/2^i$ it moves on to solve an instance of size $n-i$
  • Each instance pays a cost of $O(n)$, where $n$ is the input size of that instance

Over expectation, the runtime can be defined recursively as follows:

$T(n) = O(n) + \sum\limits_{i=0}^{n-1} (\dfrac{1}{2^{n-i+1}} T(i)) + \frac{1}{2}T(i-1)$

$T(0) = O(1)$

I have calculated that the expected number of "jumps" at each stage is $\leq 1$. I did this by showing $\sum\limits_{i=0}^\infty \dfrac{i}{2^{i+1}}= 1$ by using telescoping and geometric series. However, since the complexity at each stage diminishes as $n$ gets smaller, although this hints the runtime is $O(n^2)$, it does not prove it. Anyone have any ideas to prove a runtime for the less relaxed version?

EDIT: Slight gap in my formulation. The "$3/4$" probability for moving onto an instance of size $n-1$ should actually be larger than $3/4$ since the probabilities $1/2, 1/4, 1/8, ...$ only go on till $1/2^{n+1}$. If no jumps were made, the algorithm deterministically moves on to an instance of size $n-1$.

$\endgroup$
1
$\begingroup$

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:

  1. Since each "jump" is $O(1)$, it takes $\Omega(n)$ steps (on average) to reach $n/2$.
  2. At each of these $\Omega(n)$ steps, we pay a cost of $\Omega(n)$.
  3. 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.

$\endgroup$
  • $\begingroup$ My concern is $O(n^2)$ may not be a tight bound. Although it is expected we only make one jump, the payoffs are higher if we were to make a larger jump. I agree with your analysis if for each instance we pay a cost of $O(1)$, but shouldn't there be a way to mathematically show the expected payoff with $O(n)$ per instance still boils down to an $O(n^2)$ algorithm? Without just assuming $\Theta(original\ problem\ size)$ at each step? $\endgroup$ – Bryce Sandlund Dec 4 '14 at 0:53
  • $\begingroup$ I can't follow what you're saying. It is easy to give an $O(n^2)$ upper bound unconditionally. If you don't know anything more on the cost of each step, the best lower bound you can prove is $\Omega(n)$; indeed, if the cost at each step is $O(1)$, then the running time is $\Theta(n)$. $\endgroup$ – Yuval Filmus Dec 4 '14 at 1:00
  • $\begingroup$ My point is even though you expect to only progress one step each time, if you progress, say, all the way to the end, the next iteration has $O(1)$ runtime, since $n$ at the last iteration is $1$. So you can't make the argument by first saying you make $O(n)$ steps and then saying each step is $O(n)$ time. You must solve the recurrence, which gives a lower time complexity if you make bigger steps. $\endgroup$ – Bryce Sandlund Dec 4 '14 at 2:23
  • $\begingroup$ Right, if you get lucky the algorithm will terminate in $O(n)$. But the expected running time is $\Omega(n^2)$ (assuming the cost at each step is $\Omega(n)$). Even more is true: with high probability the running time is $\Omega(n^2)$. $\endgroup$ – Yuval Filmus Dec 4 '14 at 2:25
  • $\begingroup$ I'm not positive I fully understand, but I'll mark this as accepted, thanks for the insight. $\endgroup$ – Bryce Sandlund Dec 8 '14 at 0:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.