Divide-and-Conquer and the Master Theorem

Core Idea

Divide-and-conquer algorithms split a size-n problem into a subproblems of size n/b and combine results in O(nᵈ) time, yielding the recurrence T(n) = aT(n/b) + O(nᵈ). The Master Theorem gives the asymptotic solution: T(n) = Θ(nᵈ log n) if a = bᵈ, Θ(nᵈ) if a < bᵈ, and Θ(n^{log_b a}) if a > bᵈ. This covers merge sort (a=2, b=2, d=1 → Θ(n log n)), binary search (a=1, b=2, d=0 → Θ(log n)), and Strassen's matrix multiplication algorithm. The theorem is the primary tool for analyzing recursive algorithms.

How It's Best Learned

Apply the Master Theorem to 5-6 concrete recurrences before studying its proof. Verify each case against the recursion tree: draw the tree, compute work at each level, and sum across levels. Derive merge sort's complexity both via the theorem and by directly expanding the recursion tree.

Common Misconceptions

• Applying the Master Theorem when the combine cost does not fit the polynomial O(nᵈ) form (e.g., when combine cost has logarithmic factors).
• Forgetting to check that a ≥ 1, b > 1, and d ≥ 0 for valid application.

Explainer

Divide-and-conquer algorithms work by reducing a problem of size n to a smaller problems, each of size n/b, solving them recursively, and then combining the results. The key insight is that this recursive structure directly produces a recurrence relation — exactly the kind you studied before. If combining takes O(nᵈ) time, the total work satisfies T(n) = aT(n/b) + O(nᵈ), where a is the number of subproblems, b is the reduction factor, and d is the exponent of the combine step.

The Master Theorem solves this recurrence by comparing the rate at which work accumulates across levels of the recursion tree. Picture the recursion tree: at the top level there is O(nᵈ) combine work; at the next level there are a subproblems each of size n/b, contributing a · O((n/b)ᵈ) = O(nᵈ · a/bᵈ) total work. The ratio a/bᵈ tells you how fast work grows or shrinks per level. If a/bᵈ < 1, work shrinks geometrically and the top level dominates: T(n) = Θ(nᵈ). If a/bᵈ > 1, work grows geometrically and the leaves dominate: there are n^{log_b a} leaves, giving T(n) = Θ(n^{log_b a}). If a/bᵈ = 1, every level contributes equally and there are log_b n levels: T(n) = Θ(nᵈ log n).

Merge sort perfectly illustrates the equal-work case. It splits into a=2 subproblems of size n/2 (so b=2), and merging takes O(n) time (d=1). Check: a = 2, bᵈ = 2¹ = 2, so a = bᵈ. The Master Theorem immediately gives T(n) = Θ(n log n). Binary search, by contrast, has a=1 subproblem of size n/2 and O(1) combine work (d=0). Here a=1 and bᵈ=1, so again a = bᵈ and T(n) = Θ(log n). Strassen's algorithm for matrix multiplication has a=7, b=2, d=2, so bᵈ=4 < 7=a, meaning the leaves dominate and T(n) = Θ(n^{log₂ 7}) ≈ Θ(n².81).

The Master Theorem is powerful because it converts case analysis on the recursion tree into a quick arithmetic comparison. But be aware of its limits: it only applies when the combine cost is exactly polynomial (O(nᵈ) with no extra logarithmic factors). If the combine cost is, say, O(n log n), the standard theorem does not apply and you need the Akra-Bazzi method or direct expansion. Before applying the theorem, always verify that a ≥ 1, b > 1, and d ≥ 0 — these conditions ensure the recursion is well-formed and the tree has the geometric structure the theorem exploits.