# Median of medians algorithm

I am referring to the algorithm presented here used to find a good pivot: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

My question is I don't quite understand why the elements have to be divided specifically into groups of 5. Why not some other number?

-

The key section of the Wikipedia article says

The median-calculating recursive call does not exceed worst-case linear behavior because the list of medians is 20% of the size of the list, while the other recursive call recurse on at most 70% of the list, making the running time $$T(n) \leq T(n/5) + T(7 \cdot n/10) + O(n).$$

The O($n$) is for the partitioning work (we visited each element a constant number of times, in order to form them into $n/5$ groups and take each median in O($1$) time). From this, one can then show that $$T(n) \leq c \cdot n \cdot (1 + (9/10) + (9/10)^2 + \cdots) \in O(n).$$

using the fact that at most 70% of the list is to one side of the median of the medians with groups of five.

If instead you had groups of three the first inequality would be $$T(n) \leq T(n/3) + T(2 \cdot n/3) + O(n)$$ so you would not get a convergent series in in the second inequality.

There is no reason why you should not use something greater than five; for example with seven the first inequality would be $$T(n) \leq T(n/7) + T(5 \cdot n/7) + O(n)$$ which also works, but five is the smallest odd number (useful for medians) which works.

-
Thanks for the help! But still a little bit confused. I don't see how we get c*n*(1 + (9/10)+(9/10)^2...) E 0(n) from the aforementioned runtime. – user1782677 Nov 6 '12 at 1:10
The $c \cdot n \cdot 1$ comes from the $O(n)$ while the $c \cdot n \cdot \frac{9}{10}$ term comes from the $O(n/5) +O(7n/10)$ which will appear since $\frac{n}{5}+\frac{7n}{10} = \frac{9n}{10}$, and similarly further down the recursion. – Henry Nov 6 '12 at 7:33
Hello @Henry!!! ould you explain me how we find the recurrence relation that describes the cost of the algorithm? The algorithm is this: math.stackexchange.com/questions/1180071/… – evinda Mar 10 '15 at 17:56
@evinda: what is unclear about what Wikipedia wrote? $T(n/5)$ to find the median of medians plus $T(7n/10)$ since the median of medians divided the set at worse $30:70$ plus $O(n)$ to create the five member subsets and find their medians. – Henry Mar 10 '15 at 21:59