Quiz 3 (Solutions)

Published

June 9, 2026

CS F364: Design & Analysis of Algorithms

Quiz 3 — June 9, 2026

Coverage: Lectures 1–12

Note

Instructions:

  • Time: 15 minutes.
  • Write your answers clearly on paper, scan, and upload to Google Classroom.
  • Show all steps for full credit.

Question: Median of Medians

The Deterministic Select algorithm (Median of Medians) finds the \(i^{\text{th}}\) smallest element in \(O(n)\) time by:

  1. Dividing the \(n\) elements into groups of 5.
  2. Finding the median of each group (by brute force, \(O(1)\) per group).
  3. Recursively finding the median \(x\) of these \(\lceil n/5 \rceil\) medians.
  4. Partitioning around \(x\) and recursing on the appropriate side.

The recurrence for groups of size 5 is:

\[ T(n) \le T\left(\frac{n}{5}\right) + T\left(\frac{7n}{10}\right) + O(n) \]

(a) [2 marks] Give the recurrence \(T_3(n)\) for the Deterministic Select algorithm when groups of size 3 are used instead of 5. What fraction of elements is guaranteed to be \(\le\) the median-of-medians, and what fraction is guaranteed to be \(\ge\) it?

(b) [2 marks] Give the recurrence \(T_7(n)\) when groups of size 7 are used. What are the corresponding fractions?

(c) [1 mark] Solve \(T_3(n)\) using the substitution method (guess \(T_3(n) \le cn\) and show it fails, then state the actual asymptotic growth).

Solution

Part (a) — Groups of size 3

With group size \(3\), each group yields a median. There are \(\lceil n/3 \rceil\) group medians.

  • At least \(\lceil \lceil n/3 \rceil / 2 \rceil \approx n/6\) medians are \(\le\) the median-of-medians.
  • Each such median has \(2\) elements \(\le\) it in its group.
  • So at least \(2 \cdot \frac{n}{6} = \frac{n}{3}\) elements are \(\le\) the median-of-medians.
  • Similarly, \(\frac{n}{3}\) elements are \(\ge\) it.

Thus at most \(\frac{2n}{3}\) elements are on either side in the worst case.

\[ T_3(n) \le T\left(\frac{n}{3}\right) + T\left(\frac{2n}{3}\right) + O(n) \]

Part (b) — Groups of size 7

With group size \(7\), each group yields a median. There are \(\lceil n/7 \rceil\) group medians.

  • At least \(\lceil \lceil n/7 \rceil / 2 \rceil \approx n/14\) medians are \(\le\) the median-of-medians.
  • Each such median has \(3\) elements \(\le\) it in its group.
  • So at least \(4 \cdot \frac{n}{14} = \frac{2n}{7}\) elements are \(\le\) the median-of-medians.
  • Similarly, \(\frac{2n}{7}\) elements are \(\ge\) it.

Thus at most \(\frac{5n}{7}\) elements are on either side in the worst case.

\[ T_7(n) \le T\left(\frac{n}{7}\right) + T\left(\frac{5n}{7}\right) + O(n) \]

Part (c) — Solving \(T_3(n)\)

Guess: \(T_3(n) \le cn\).

\[ \begin{aligned} T_3(n) &\le T(n/3) + T(2n/3) + cn \\ &\le c\cdot\frac{n}{3} + c\cdot\frac{2n}{3} + cn \\ &= cn\left(\frac{1}{3} + \frac{2}{3} + 1\right) \\ &= cn(2) \\ &> cn \quad \text{(since } 2 > 1 \text{)} \end{aligned} \]

The guess fails — the coefficients sum to \(> 1\), so the recursion tree does not geometrically decay.

With \(a/b = 1/3 + 2/3 = 1\), the actual growth is \(T_3(n) = \Theta(n \log n)\) (see Quiz 2 for the reasoning: when the coefficients sum to \(1\), each level contributes \(O(n)\) and there are \(O(\log n)\) levels).

Summary

Group size Reductions Recurrence Complexity
3 \(2n/3\) \(T(n/3) + T(2n/3) + O(n)\) \(O(n \log n)\)
5 \(7n/10\) \(T(n/5) + T(7n/10) + O(n)\) \(O(n)\)
7 \(5n/7\) \(T(n/7) + T(5n/7) + O(n)\) \(O(n)\)

Group sizes of \(5\) (or \(7\), \(9\), etc.) make the coefficients sum to \(< 1\), giving geometric decay and \(O(n)\) time.