Exercises — Linear time selection — median of medians algorithm

(a) FALSE. The whole point is to find one order statistic without paying the $O(n\log n)$ of sorting; we only partition, never fully sort. (b) TRUE. Sorted position 1 is the smallest element, i.e. the minimum. (c) TRUE. This is exactly the recurrence proven in the parent note — one recursive call on the $n/5$ medians, one on the surviving side of size $\le 7n/10$, plus $O(n)$ linear work $cn$.

Groups of 5; at least $\frac{3n}{10}$ elements $\le M$; the second fraction is $\frac{7}{10}$; their sum must be less than 1. Here $\frac{1}{5}+\frac{7}{10}=\frac{9}{10}<1$. ✓

Groups of 5 (in order): [25,4,13,8,40] [2,17,33,6,11] [29,7,1,20,9] Sort each, take the middle (3rd of 5):

• [4,8,13,25,40] → median 13
• [2,6,11,17,33] → median 11
• [1,7,9,20,29] → median 9 Median of medians of [13,11,9]: sorted [9,11,13] → middle is 11. So $M=11$.

Walk the array and bucket each element around $M=11$:

• $L$ (< 11): [4, 8, 2, 6, 7, 1, 9] → $|L|=7$.
• $E$ (= 11): [11] → $|E|=1$.
• $G$ (> 11): [25, 13, 40, 17, 33, 29, 20] → $|G|=7$. Positions: $L$ occupies ranks $1\dots 7$, $E$ occupies rank $8$, $G$ occupies ranks $9\dots 15$. Since $k=8$ and $|L|=7$, we have $k\le |L|+|E|=8$ but $k>|L|=7$, so $k$ lands inside $E$ → the answer is $M=11$. No further recursion needed. (Check: 11 is indeed the 8th smallest — the median — of the 15 numbers.)

With $n=25$ there are $n/5=5$ groups, so 5 group-medians. $M$ is the median of these 5, so at least 3 of them are $\le M$ (the median itself plus the two below it — that is $\lceil 5/2\rceil =3$). Now look at each of those 3 groups whose median is $\le M$ (blue-shaded column in the figure). Inside such a group, the median plus the 2 elements smaller than it are all $\le M$ — that is 3 of the 5 elements per group. Guaranteed smaller: $3\text{ groups}\times 3\text{ elements}=9$ elements $\le M$. Compare to the formula $\frac{3n}{10}=\frac{3\cdot 25}{10}=7.5$. Our exact count $9\ge 7.5$ ✓ — the $\frac{3n}{10}$ figure is a lower bound (it drops boundary/partial groups), and the true count is a bit better.

At least $\frac{3n}{10}$ elements are $\le M$ and (by mirror symmetry) at least $\frac{3n}{10}$ are $\ge M$. So the side we do not recurse into contains at least $\frac{3n}{10}$ elements, meaning the side we do recurse into is at most $n-\frac{3n}{10}=\frac{10n-3n}{10}=\frac{7n}{10}.$ That $\frac{7n}{10}$ is exactly the second recursive size in the recurrence.

Guess $T(m)\le am$ for all $m<n$ and substitute: $T(n)\le a\cdot \frac{n}{5}+a\cdot \frac{7n}{10}+cn=\frac{an}{5}+\frac{7an}{10}+cn.$ Combine the $a$-terms: $\frac{1}{5}+\frac{7}{10}=\frac{2}{10}+\frac{7}{10}=\frac{9}{10}$, so $T(n)\le \frac{9an}{10}+cn.$ We want this $\le an$. So require $\frac{9an}{10}+cn\le an$, i.e. $cn\le an-\frac{9an}{10}=\frac{an}{10}$, i.e. $a\ge 10c.$ Smallest valid constant: $a=10c$. Then $T(n)\le 10cn=O(n)$. Linear worst-case. ∎

Substitute $T(m)\le am$: $T(n)\le a\cdot \frac{n}{7}+a\cdot \frac{5n}{7}+cn=\frac{6an}{7}+cn.$ (Since $\frac{1}{7}+\frac{5}{7}=\frac{6}{7}<1$.) Require $\frac{6an}{7}+cn\le an$: $cn\le an-\frac{6an}{7}=\frac{an}{7}$, so $a\ge 7c$. Smallest constant $a=7c$, giving $T(n)\le 7cn=O(n)$ — still linear, with a smaller constant factor $7c$ than the $10c$ of group-5 (though group-5 keeps per-group median-finding cheaper, which is why 5 wins in practice).

Groups of 3: half of $n/3$ medians are $\le M$, and each such group contributes 2 elements $\le M$ (the median plus one smaller). Guaranteed $\le M$: $2\cdot \frac{1}{2}\cdot \frac{n}{3}=\frac{2n}{6}=\frac{n}{3}$. Surviving side $\le n-\frac{n}{3}=\frac{2n}{3}$. Recurrence: $T(n)\le T\left(\frac{n}{3}\right)+T\left(\frac{2n}{3}\right)+cn.$ Substitute $T(m)\le am$: $T(n)\le a\frac{n}{3}+a\frac{2n}{3}+cn=an+cn$. The $a$-terms sum to $\frac{1}{3}+\frac{2}{3}=1$, giving $T(n)\le an+cn$. To close we'd need $an+cn\le an$, i.e. $cn\le 0$ — impossible for $c>0$. The extra $cn$ per level never gets absorbed; over $\Theta (\log n)$ levels it stacks to $\Theta (n\log n)$ (in fact the pivot guarantee alone doesn't even bound it that tightly). So group-3 is not linear. ∎

Feed an already-sorted array [1,2,3,...,n] and ask for $k=n$ (the maximum). First-element pivot is always the current minimum: partition puts everything into $G$ and the pivot lands at rank 1, so we recurse on the remaining $n-1$ elements — one element peeled per call. Work is $cn+c(n-1)+c(n-2)+\cdots +c\cdot 1=c\cdot \frac{n(n+1)}{2}=\Theta (n^2).$ Why MoM defeats this: the MoM pivot $M$ always has $\ge \frac{3n}{10}$ elements on each side, so no call can peel off just one element — every recursion discards a constant fraction, capping the depth at $O(\log n)$ and the total at $O(n)$. There is no input that makes MoM's pivot an extreme.

A single MoM call spawns two recursive Select calls: one on the $n/5$ medians (to find $M$), and one on the surviving side $\le 7n/10$. Randomized Quickselect spawns one recursive call (into the surviving side only) and pays $O(1)$ to pick its pivot. So per level MoM does strictly more work — extra median-finding, extra buffer for medians, a second recursion — inflating the hidden constant (roughly $10c$ vs. a small expected constant for random). Conclusion: MoM guarantees $O(n)$ worst-case but loses on the constant; use it when adversarial or real-time guarantees matter, otherwise prefer randomized Quickselect / introselect.

Smallest constant $a$ for group-5 MoM ::: $a=10c$, giving $T(n)\le 10cn$. Smallest constant $a$ for group-7 MoM ::: $a=7c$. Exact count of elements guaranteed $\le M$ for $n=25$ ::: at least $9$ (formula lower bound $3n/10=7.5$). Worst-case work of first-pivot Quickselect on sorted input asking for the max ::: $cn(n+1)/2=\Theta (n^2)$. Why group-3 fails, in one phrase ::: fractions sum to $1/3+2/3=1$, so substitution needs $cn\le 0$ — impossible.