Questions: Divide-and-Conquer and the Master Theorem

Question 1

An algorithm has recurrence T(n) = 3T(n/9) + O(n). What is its asymptotic complexity?

• A. Θ(n log n) — because there are logarithmically many levels
• B. Θ(n) — because the top-level work dominates
• C. Θ(√n · log n) — because a = b^d with a logarithmic factor
• D. Θ(n^(log₉ 3)) — because the leaves dominate

Answer: (B)

Here a=3, b=9, d=1, so b^d = 9^1 = 9 > 3 = a. Since a < b^d, the work at the top level dominates and T(n) = Θ(n^d) = Θ(n). Option D applies only when a > b^d (leaves dominate). Option A is the equal-work case (a = b^d). Checking which case applies first is the essential first step — do the arithmetic on a, b^d before anything else.

Question 2

A student wants to apply the Master Theorem to the recurrence T(n) = 2T(n/2) + O(n log n). Why does the standard Master Theorem fail here?

• A. Because a = b^d, the theorem always gives an ambiguous answer in this case
• B. Because the combine cost O(n log n) is not purely polynomial — it has a logarithmic factor
• C. Because a=2 and b=2 are equal, violating the requirement a ≠ b
• D. Because d=1 is not large enough to apply the theorem

Answer: (B)

The Master Theorem requires the combine cost to be exactly Θ(n^d) for some constant d. When the combine cost has an extra logarithmic factor — O(n log n) rather than O(n) — the theorem's case conditions do not cleanly apply. This is a common pitfall: merge sort works because its combine is O(n), not O(n log n). For such recurrences, the Akra-Bazzi method or direct expansion is needed. Options A, C, and D describe non-existent restrictions.

Question 3

Merge sort's recurrence T(n) = 2T(n/2) + O(n) falls into the a = b^d case of the Master Theorem.

• T. True
• F. False

Answer: True

With a=2, b=2, and d=1, we compute b^d = 2^1 = 2 = a. This is the equal-work case, where every level of the recursion tree contributes the same amount of work (O(n) per level), and there are log₂ n levels, yielding T(n) = Θ(n log n). A common mistake is to say 'a > b^d' because there are two subproblems, but what matters is the comparison a vs. b^d, not a vs. b alone.

Question 4

For the recurrence T(n) = 4T(n/2) + O(n³), the leaves of the recursion tree dominate the total work.

• T. True
• F. False

Answer: False

Here a=4, b=2, d=3, so b^d = 2³ = 8. Since a=4 < b^d=8, the top-level work dominates and T(n) = Θ(n^d) = Θ(n³). The leaves dominate only when a > b^d (work grows going down the tree). Here work shrinks geometrically with depth, so almost all the work is at the root level. This is the opposite of what intuition might suggest — 4 subproblems sounds like a lot, but heavy O(n³) combining work at the top overwhelms the contribution from deep levels.

Question 5

Explain what the ratio a/b^d reveals about the structure of a divide-and-conquer recursion tree, and how it determines which Master Theorem case applies.

Model answer: The ratio a/b^d measures how work grows or shrinks from one level of the recursion tree to the next. At the top level there is O(n^d) combine work; one level down there are a subproblems each contributing a·O((n/b)^d) = O(n^d · a/b^d) total work. If a/b^d < 1, work shrinks geometrically toward the leaves and the top level dominates (Θ(n^d)). If a/b^d > 1, work grows and the leaf level dominates (Θ(n^(log_b a))). If a/b^d = 1, every level contributes equally across log_b n levels (Θ(n^d log n)).

This is the geometric-series insight at the heart of the theorem. Most students memorize the three cases as formulas without understanding that they all follow from the same question: does the per-level work increase, decrease, or stay constant as you descend the tree? The recursion tree makes the cases intuitive rather than arbitrary.