Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am referring to the algorithm presented here used to find a good pivot:

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?

share|cite|improve this question

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.

share|cite|improve this answer
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:… – 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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