Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.