Let $A$ be a randomised algorithm and $F$ be a function such that $A$ returns $F(x)$ on any input $x$. Furthermore suppose that, for input $x$ of size $n$, the $\textbf{expected}$ running time of $A$ is $O(n)$. Give an algorithm that is guaranteed to terminate in time $O(n)$ for every input, and which on input $x$ outputs $F(x)$ with probability at least $1-\varepsilon$ and otherwise returns ${\tt timeout}$.

Is there a way to do it with somehow derandomizing $A$ and using the timeout possibility in a clever way? I have no other ideas. Any help appreciated!


Write $T_x$ for the random variable representing the running time of $A$ on input $x$. By Markov's inequality,

$$\Pr(T_x \geq 2 \operatorname{E}(T_x)) \leq \frac{1}{2}.$$

See if you can figure out a solution now.


Choose $N$ so that $2^{-N} < \varepsilon$. For $1..N$, repeat the following: simulate $A(x)$ for $2 \operatorname{E}(T_x)$ steps with fresh independent random bits; if a value is returned from this simulation, then return that immediately. If we reach the end of the loop and none of the $N$ simulations returned a value, then return timeout.

  • $\begingroup$ Hence for an integer constant $N$ such that $(\frac{1}{2})^N < \varepsilon$ we have that $N$ trials will suffice, i.e. our new algorithm is "Launch $A$ exactly $N$ times and at the trials at which it does not stop in $O(n)$ time, stop it manually and put timeout". Then we have that with probability $1-\varepsilon$ in at least one of these trials it will stop in $O(n)$ time. Does this work? $\endgroup$ – DesmondMiles Feb 6 at 13:35
  • 1
    $\begingroup$ @DesmondMiles That's the general idea, yeah. The way you wrote it is missing a couple details though, such as exactly how long you have to run $A$ for each time for this particular proof to go through. See my edit to the answer. $\endgroup$ – Aaron Rotenberg Feb 6 at 14:02

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.