Given only the expected runtime of an algorithm, what can Markov's inequality tell us about its worst-case runtime?

Question

The following is exercise 3.8 from the first edition of Mitzenmacher and Upfal's Probability and Computing: Randomized Algorithms and Probabilistic Analysis.

Suppose that we have an algorithm that takes as input a string of $n$ bits. We are told that the expected running time is $O(n^2)$ if the input bits are chosen independently and uniformly at random. What can Markov's inequality tell us about the worst-case running time of this algorithm on inputs of size $n$?

Unlike most of the other exercises in the book which request either a proof or a numerical answer, the response expected in this problem is so open-ended that I can't easily verify the correctness (or more importantly in this case, the completeness) of my solution. I am concerned that I may have missed something that Markov's inequality may give us in my solution below.

My Solution:

Let $W(n)$ be the worst case runtime of the algorithm on an input of length $n$. Let $R_n$ be the random variable denoting the runtime of the algorithm on an input of length $n$. By Markov's inequality,

$$\Pr(R_n \geq W(n)) \leq \frac{O(n^2)}{W(n)}$$.

Since $W(n)$ is nonnegative, rearranging gives

$$W(n) \leq \frac{O(n^2)}{\Pr(R_n \geq W(n))}$$

or alternatively,

$$W(n) = O\left( \frac{n^2}{\Pr(R_n \geq W(n))} \right)$$.

This result is intuitive to me: the greater the probability that the algorithm assumes its worst case running time, the lower the worst case running time must be so as to preserve the mean running time (and vice-versa). Is there anything else that I am missing?

Answer 1

Using Markov's inequality, you can get a range of running times with different probabilities. For example,

1. $$\Pr(R_n \leq O(n^2)) \geq 1 - c, \quad \textrm{for some constant $c<0$}$$.

2. $$\Pr(R_n \leq O(n^3)) \geq 1 - \frac{c}{n}, \quad \textrm{for some constant $c<0$}$$.

3. $$\Pr(R_n \leq O(n^4)) \geq 1 - \frac{c}{n^2}, \quad \textrm{for some constant $c<0$}$$.

and so on...

It means the worst-case time complexity could also be $\infty$. But the probability of happening that is super low (tending to $0$).

Also, note that for sufficiently large $n$, the probability of getting $o(n^2)$ is very good. For example, for any small constant $\epsilon >0$,

$$\Pr(R_n \leq O(n^{2+\epsilon})) \geq 1 - \frac{c}{n^{\epsilon}}, \quad \textrm{for some constant $c<0$}$$.