Break the array into groups of five, take each group's median, and take the median of those medians as the pivot — recursively. The pivot is then guaranteed to lie in the middle forty per cent, so at least 3n/10 elements are discarded and the recurrence is T(n) ≤ T(n/5) + T(7n/10) + cn. That is linear because 1/5 + 7/10 is less than one, and with groups of three the same two fractions sum to exactly one and it is not.
Core ideas
The hard idea is that the two fractions of a two-term recurrence decide everything, and that they are decided in turn by the group size.
Let p be the median of the ⌈n/5⌉ group medians. At least half of those medians are at most p, and each of their groups contributes three elements at most p — its median and the two below it. So at least 3⌈⌈n/5⌉/2⌉ elements are at most p, which is about 3n/10, and symmetrically about 3n/10 are at least p. The pivot is not the median and does not need to be: it is guaranteed to sit in the middle forty per cent.
The recurrence has two recursive terms — one call on the n/5 medians to find the pivot, one on the at most 7n/10 survivors — so the master theorem does not apply. The recursion tree does: level zero costs cn, level one costs c(1/5 + 7/10)n, level two c(9/10)²n, and the sum is geometric with ratio 9/10, giving 10cn. The lab evaluates those level sums as exact fractions, and at n = 45 they total exactly 450 = 10n.
On the lab's 45-element array, median of medians spends 299 comparisons and quickselect spends 131 for the same rank. That is the price of removing the word “expected”: quickselect is linear in expectation with a small constant, median of medians is linear on every input with a large one. In practice the two are combined, and the theoretical value of this one is that it makes the deterministic bound available at all.
The material
The counting argument for the discard, the level sums that solve a two-term recurrence, and what group size three does to them.
To choose a pivot of a[1..n] by median of medians with group size g: split the array into ⌈n/g⌉ groups of g consecutive elements, find each group's median by direct sorting, and return the median of those ⌈n/g⌉ medians, found by applying the whole selection algorithm to them recursively.
With groups of five, the median of medians p has at least 3(⌈⌈n/5⌉/2⌉ − 2) elements at most p and at least as many at least p. Asymptotically that is 3n/10, so at most 7n/10 elements survive the partition.
Half of the ⌈n/5⌉ group medians are at most p, by the definition of a median. Take any such group: its own median is at most p, and so are the two elements of that group below its median. That is three elements at most p from each of those groups.
Two groups have to be set aside: the group containing p itself, and the last group if it is not full. That is where the − 2 comes from. Everything else is symmetric for the elements at least p.
So at least about 3n/10 elements are on each side of the pivot, and the side that survives the partition holds at most n − 3n/10 = 7n/10 of them.
□
So the whole argument is one comparison of a sum with one, and the lab does it as a comparison of integers: 1/5 + 7/10 = 9/10 and 1/3 + 2/3 = 1 are computed as exact rationals, because 0.8999999999999999 is not an argument. Groups of seven give 1/7 + 5/7 = 6/7, which also converges, and at n = 45 the level sums total 315 = 7n.
The lab's array at n = 45 is a seeded shuffle of 1 … 45. Its nine group medians are 24 35 21 27 14 38 8 16 25, and the median of those is 24. Partitioning around 24 leaves 23 elements below and 21 above. The guarantee for this size and group is 9, so the round discarded 21 where it had promised 9 — and the promise is the part that holds for every array of 45 elements.
That gap between 9 and 21 is the slack a proof about every input gives away, and the lab prints both numbers on every round rather than only the one that flatters the algorithm. Note also that the pivot 24 is not the median of 1 … 45, which is 23. It never had to be.
The group size g fixes both fractions: the median recursion is on n/g elements, and the guaranteed discard is (g+1)/(4g), so the survivor fraction is 1 − (g+1)/(4g). At g = 3 those are 1/3 and 2/3, summing to exactly one, and a recursion tree whose levels do not shrink costs n at each of about log n levels. At g = 5 they sum to 9/10 and the tree is geometric. Three is not slightly worse; it is a different complexity class.
Larger groups keep the sum below one — seven gives 6/7 — while raising the constant cost of sorting each group, so five is the smallest odd size that works and is the one everybody uses. The lab lets you set all three and prints the level sums for each, so the claim is checkable rather than received.
Interactive
Groups of three, five and seven, and the sum that decides which of them is linear
Method
The pivot selection is mechanical. The part worth slowing down for is the level sums.
Groups of five, in order, and sort each one by hand — five elements is a handful of comparisons and the constant is why the group size cannot grow much. Write the medians out as their own list.
This is the same problem on a fifth of the data, which is the first recursive term. On 45 elements the list of medians has nine entries and its median is the pivot.
Count how many elements fell on each side. The lab prints the guarantee for that round beside the smaller side; the actual figure is normally far larger, and that difference is the price of a claim that covers every array rather than this one.
T(n) ≤ T(n/g) + T(1 − (g+1)/(4g))n + cn. Add the two fractions. If the sum is below one, the level sums are geometric and total n/(1 − sum); if it is one, every level costs n and there are about log n of them.
299 against 131 at 45 elements. Both are one input's cost. The claim that distinguishes the two algorithms is not in those numbers: it is that one of them holds for every array and the other holds in expectation.
The array is the lab's seeded shuffle of 1 … 45, taken in order, nine groups of five. Each group is sorted and its median taken; the median of the nine medians is the pivot.
Check the guarantee against the round. Five of the nine medians are at most 24, and each of their groups contributes three elements at most 24; setting aside the group holding the pivot leaves four groups, so twelve elements are guaranteed below, and the lab's per-round figure of 9 is the same count with the partial-group allowance made. The round actually delivered 23. The guarantee is the number that survives being asked about every array.
The level sums are the other half. 45, 40.5, 36.45, … is a geometric sequence with ratio 9/10, and 45/(1 − 9/10) = 450. Switch the group size to three in the lab and the level sums become 45, 45, 45, … — the column stops shrinking, and there is no total to print.
For a faded rehearsal, set the group size to seven and predict two things before reading them: the two fractions, and whether the tree converges. The supplied first move is the discard formula (g+1)/(4g), which at g = 7 is 8/28 = 2/7. Work out the survivor fraction and the sum, then say why seven is not used in practice even though its sum is smaller than five's.
You should be able to run one round of the pivot selection on paper, state the discard guarantee and where the − 2 comes from, solve the two-term recurrence by its level sums, and say what changes at group size three and why it is a change of class.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.