Questions: Divide-and-Conquer Recurrences and the Master Theorem

Question 1

An algorithm divides a problem of size n into 9 subproblems each of size n/3 and does O(n) combining work. Which case of the Master Theorem applies, and what is the runtime?

• A. Case 2: T(n) = Θ(n log n) because the combining work and leaf work are similar
• B. Case 1: T(n) = Θ(n²) because n^(log₃ 9) = n² dominates f(n) = n
• C. Case 3: T(n) = Θ(n) because the combining work f(n) = O(n) dominates at the root
• D. Case 1: T(n) = Θ(n) because f(n) = O(n) is already a simple expression

Answer: (B)

Here a=9, b=3, so n^(log₃ 9) = n². Since f(n) = Θ(n) is polynomially smaller than n² (by ε=1), Case 1 applies: leaf work dominates and T(n) = Θ(n²). Option C is the classic confusion: the root does O(n) work, but the leaves collectively do Θ(n²) work total — which is far more. Option A might feel right because n and n² are 'in the same ballpark,' but Case 2 requires f(n) ≈ n^(log_b a), and n is polynomially — not just logarithmically — smaller than n².

Question 2

For merge sort, a=2, b=2, f(n)=Θ(n), and n^(log₂ 2)=n. The Master Theorem gives T(n)=Θ(n log n). What does the recursion tree tell us about WHY a log factor appears?

• A. The log factor comes from the tree's height: work is distributed uniformly across all O(log n) levels, each doing Θ(n) total work
• B. The log factor appears because f(n) is too large for Case 1 but not large enough for Case 3, so extra counting is needed
• C. The log factor comes because leaf work (Θ(n)) exceeds root work, requiring an adjustment term
• D. The log factor accounts for memory allocation overhead at each recursive call level

Answer: (A)

Case 2 applies when f(n) ≈ n^(log_b a) — work spreads evenly across every level of the recursion tree. Merge sort's tree has Θ(log n) levels, and each level does Θ(n) total work (n/2 merges at depth 1, n/4 + n/4 at depth 2, etc., each level summing to n). Multiply: Θ(n) × Θ(log n) = Θ(n log n). The log factor is literally the height of the tree. Option B is a description of the theorem's boundary conditions, not an explanation of where the log comes from geometrically.

Question 3

The quantity n^(log_b a) in the Master Theorem represents the total work done at the root of the recursion tree.

• T. True
• F. False

Answer: False

n^(log_b a) = a^(log_b n) is the number of leaf nodes in the recursion tree — it represents the total base-case work at the leaves, not the root's work. The root does f(n) work. This distinction is exactly what the three cases capture: Case 1 means leaves dominate (n^(log_b a) > f(n)), Case 3 means root dominates (f(n) > n^(log_b a)), and Case 2 means they balance. Confusing the leaf count with root work reverses the meaning of Cases 1 and 3.

Question 4

If T(n) = 2T(n/2) + Θ(n²), Case 3 of the Master Theorem applies because f(n) = Θ(n²) is polynomially larger than n^(log₂ 2) = n.

• T. True
• F. False

Answer: True

n^(log₂ 2) = n¹ = n. Since f(n) = Θ(n²) = Ω(n^(1+1)), the polynomially-larger condition for Case 3 is satisfied (with ε=1). The regularity condition also holds: a·f(n/b) = 2·(n/2)² = n²/2 ≤ (1/2)·n², satisfying af(n/b) ≤ cf(n) for c=1/2 < 1. So T(n) = Θ(n²) — the combining step is the bottleneck, and all the recursive work is negligible by comparison.

Question 5

Explain the core intuition behind the Master Theorem's three cases using the recursion tree. What is the theorem really asking?

Model answer: The recursion tree has O(log_b n) levels. At each depth k, there are a^k nodes each doing f(n/b^k) work. The per-level total is a^k · f(n/b^k). The Master Theorem asks: does this per-level work grow (leaves dominate → Case 1), stay constant (uniform spread → Case 2), or shrink (root dominates → Case 3) as you go deeper?

Seeing the cases geometrically removes the mystery. Case 1: work concentrates at the leaves — the recursion fans out into many small subproblems. Case 2: work is even across O(log n) levels, so you pick up exactly one log factor. Case 3: work concentrates at the root — the combining step is the expensive part, and recursive calls add only constant overhead. The comparison f(n) vs. n^(log_b a) is a shortcut for determining which regime applies, but the recursion tree picture shows *why* each regime gives the answer it does.