TAOCP 5.3.3 Exercise 18

The median-of-medians algorithm (Blum, Floyd, Pratt, Rivest, Tarjan) finds the \(t\)th largest element by recursively using a pivot obtained as the median of medians of small groups.

taocpmathematicsalgorithmsvolume-3math-medium

Section 5.3.3: Minimum-Comparison Selection

Exercise 18. [M20] If groups of size 5, not 7, had been used in the proof of Theorem L, what theorem would have been obtained?

Verified: no
Solve time: 6m20s

Solution

The median-of-medians algorithm (Blum, Floyd, Pratt, Rivest, Tarjan) finds the (t)th largest element by recursively using a pivot obtained as the median of medians of small groups. The proof of Theorem L in the text uses groups of size (7); changing the group size to (5) changes the constant in the resulting linear upper bound.

Median-of-medians with group size (g)

Let (g \ge 3) be odd. To select the (t)th largest of (n) elements:

  1. If (n) is below a fixed threshold, solve directly.
  2. Partition the (n) elements into (\lceil n/g \rceil) groups of size (g) (the last group may be smaller).
  3. Find the median of each group. Let (m(g)) be the number of comparisons required for this step per group; the total is (m(g)\lceil n/g \rceil).
  4. Recursively find the median (p) of these (\lceil n/g \rceil) medians.
  5. Compare every element with (p) ((n-1) comparisons) to partition the set into elements (< p) and (> p).
  6. Recurse on the appropriate part.

The pivot (p) is guaranteed to be larger than at least (\frac{g+1}{2} \cdot \frac{1}{2}\lceil n/g \rceil \approx n(g+1)/(4g)) elements, and symmetrically smaller than at least that many. Hence the larger side has size at most [ n - \frac{g+1}{2}\left\lfloor\frac{\lceil n/g \rceil}{2}\right\rfloor \le \frac{3g-1}{4g},n + O(1). ]

The worst-case number of comparisons (T(n)) therefore satisfies the recurrence [ T(n) = T!\left(\left\lceil\frac{n}{g}\right\rceil\right) + T!\left(\left\lceil\frac{3g-1}{4g}n\right\rceil\right) + m(g)\left\lceil\frac{n}{g}\right\rceil + n - 1 . ]

Asymptotically, (T(n) \sim C n) where [ C = \frac{m(g)/g + 1}{1 - 1/g - (3g-1)/(4g)} = \frac{4\bigl(m(g)+g\bigr)}{g-3}. ]

Application to Theorem L

In the proof of Theorem L the text uses (g = 7). The minimum number of comparisons to find the median of (7) elements is (m(7) = 10). Substituting gives [ C = \frac{4(10+7)}{7-3} = 17 . ] Thus Theorem L states that the median (and indeed any (t)th largest) can be found with at most (17n + o(n)) comparisons, i.e. [ V_t(n) \le 17n + o(n) \qquad (1 \le t \le n). ]

Using groups of size (5)

For (g = 5) the optimal median finding uses (m(5) = 6) comparisons. The same recurrence yields [ C = \frac{4(6+5)}{5-3} = 22 . ]

Therefore, if groups of size (5) had been used in the proof of Theorem L, the resulting theorem would be:

Theorem. The (t)th largest of (n) elements can be determined with at most (22n + o(n)) comparisons. In the notation of the section, [ V_t(n) \le 22n + o(n) \qquad \text{for all } 1 \le t \le n. ]

∎

\boxed{V_t(n) \le 22n + o(n)\ \text{for all}\ 1 \le t \le n}