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?