Give a randomized algorithm to find the median that has an expected number of comparisons = 2n + o(n)

Question

Any help would be very much appreciated.

I'm aware of 2 types of algorithms: "Median of the medians"

and one using guards like here:

http://www.cs.nthu.edu.tw/~wkhon/random12/lecture/lecture9.pdf

btw if someone can give a very explicit idea about exactly why such an algorithm gives 2n+(o) comparisons I'd really appreciate it (as I'm not too good with big O and little o notation so examples are good)

Thanks

Answer 1

Here is a solution that gives an expected number in $2n + o(n)$, but it is $n(n-1)/2$ is the worst case.

Let $L=(l_i)$ the input list.

With $n-1$ comparisons with l_0, you can split it into 2 lists of lower and upper values. The median is in the largest list. Let's say $a$ and $b$ are their sizes abd $a<b$ and $l_0$ is not the median:

$$0 \leq a < \frac{n-1}{2} < b \leq n-1 $$

The median is in the list of size $b$.

With $b-1$ more comparisons, you will get 2 lists of size $c$ and $d$. 3 possibilities :

• $ a+c = \frac{n-1}{2}$ or $\frac{n-1}{2} = d$ : you found your median
• $ a+c < \frac{n-1}{2} < d$ : the median is in the list of upper values(the less likely)
• $ a+c > \frac{n-1}{2} > d$ : the median is in the list of lower values(the more likely)

You can continue this recursively until you found your median. To calculate exactly the complexity is a bit more complicated and would need to write properly the algorithms.

Note: it is possible to implement a faster algo. Instead of picking a random (or the first) element of a list, choose one between 3 (or 5 or 7..) to have more chance to split the list were you want. Your goal is to have the median in the smallest list. You might need some tries to find the best strategy.