The usual simple algorithm for finding the median element in an array $A$ of $n$ numbers is:
- Sample $n^{3/4}$ elements from $A$ with replacement into $B$
- Sort $B$ and find the rank $|B|\pm \sqrt{n}$ elements $l$ and $r$ of $B$
- Check that $l$ and $r$ are on opposite sides of the median of $A$ and that there are at most $C\sqrt{n}$ elements in $A$ between $l$ and $r$ for some appropriate constant $C > 0$. Fail if this doesn't happen.
- Otherwise, find the median by sorting the elements of $A$ between $l$ and $r$
It's not hard to see that this runs in linear time and that it succeeds with high probability. (All the bad events are large deviations away from the expectation of a binomial.)
An alternate algorithm for the same problem, which is more natural to teach to students who have seen quick sort is the one described here: Randomized Selection
It is also easy to see that this one has linear expected running time: say that a "round" is a sequence of recursive calls that ends when one gives a 1/4-3/4 split, and then observe that the expected length of a round is at most 2. (In the first draw of a round, the probability of getting a good split is 1/2 and then after actually increases, as the algorithm was described so round length is dominated by a geometric random variable.)
So now the question:
Is it possible to show that randomized selection runs in linear time with high probability?
We have $O(\log n)$ rounds, and each round has length at least $k$ with probability at most $2^{-k+1}$, so a union bound gives that the running time is $O(n\log\log n)$ with probability $1-1/O(\log n)$.
This is kind of unsatisfying, but is it actually the truth?