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.

  • $\begingroup$ 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. $\endgroup$ – user1782677 Nov 6 '12 at 1:10
  • $\begingroup$ 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. $\endgroup$ – Henry Nov 6 '12 at 7:33
  • $\begingroup$ 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/… $\endgroup$ – evinda Mar 10 '15 at 17:56
  • $\begingroup$ @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. $\endgroup$ – Henry Mar 10 '15 at 21:59
  • $\begingroup$ Three and four work too, see my answer below. $\endgroup$ – Ecir Hana Sep 2 '16 at 9:27

You can use other block sizes as well, such as 3 or 4, as shown in the paper Select with groups of 3 or 4 by K. Chen and A. Dumitrescu (2015). The idea is to use the "median of medians" algorithm twice and partition only after that. This lowers the quality of the pivot but is faster. In the paper they call it "The Repeated Step Algorithm".

So instead of:

T(n) <= T(n/3) + T(2n/3) + O(n)
T(n) = O(nlogn)

one gets:

T(n) <= T(n/9) + T(7n/9) + O(n)
T(n) = Theta(n)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.