# From a randomized algorithm with expected time $O(n)$ to a reliable with determined running time

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}.$$
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.
• 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? – DesmondMiles Feb 6 at 13:35
• @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. – Aaron Rotenberg Feb 6 at 14:02