TAOCP 5.3.3 Exercise 8
Let the selection algorithm be modified so that the input is partitioned into groups of 5 instead of groups of 7, and the median-of-medians is used as the pivot exactly as in the proof of Theorem L.
Section 5.3.3: Minimum-Comparison Selection
Exercise 8. [M20] [M20] If groups of size 5, not 7, had been used in the proof of Theorem L, what theorem would have been obtained?
Verified: yes
Solve time: 2m22s
Let the selection algorithm be modified so that the input is partitioned into groups of 5 instead of groups of 7, and the median-of-medians is used as the pivot exactly as in the proof of Theorem L.
Step 1: Structure of the recurrence
Partition the $n$ elements into $\lceil n/5\rceil$ groups of 5 and take the median (third smallest) of each group. Let $x$ be the median of these medians.
At least half of the group medians are $\ge x$, so at least $\frac{1}{2}\cdot \frac{n}{5} = \frac{n}{10}$ groups have median $\ge x$. In each such group, at least 3 elements are $\ge$ the group median, hence at least $\frac{3n}{10}$ elements are $\ge x$. Symmetrically, at least $\frac{3n}{10}$ elements are $\le x$.
Therefore, after partitioning around $x$, the larger recursive subproblem has size at most $\frac{7n}{10}$. The algorithm also recursively finds the median of the $\lceil n/5\rceil$ medians.
Thus the running time satisfies
$$ T(n) \le T(n/5) + T(7n/10) + cn $$
for some constant $c$.
Step 2: Consequence of the recurrence
We prove by substitution that $T(n) \le an$ for a sufficiently large constant $a$.
Assume $T(k) \le ak$ for all $k < n$. Then
$$ T(n) \le a\frac{n}{5} + a\frac{7n}{10} + cn = a\frac{9n}{10} + cn. $$
Thus
$$ T(n) \le an \quad \text{whenever} \quad \frac{a}{10}n \ge cn, $$
which holds for all $n$ if $a \ge 10c$. Hence $T(n) = O(n)$.
Step 3: The resulting theorem
The proof shows that replacing groups of 7 by groups of 5 still yields a linear-time selection algorithm. No change in the qualitative structure of the argument is required: the pivot selection still guarantees a constant fraction of elements are discarded at each step, and the recursion remains linear.
Therefore, the theorem obtained is the same as Theorem L in form:
Deterministic linear-time selection still holds: the $i$th smallest of $n$ elements can be found in $O(n)$ comparisons in the worst case by the median-of-medians method using groups of 5 (with a different constant hidden in the linear bound).
No explicit constant bound is determined or needed; only the existence of a linear bound changes the statement exactly as in Theorem L.