Master Theorem

What Is a Recurrence Relation?

Many algorithms — particularly divide-and-conquer ones — call themselves recursively on smaller subproblems. Their running time can be described by a recurrence relation: an equation that expresses T(n) (the time to solve a problem of size n) in terms of T on smaller inputs.

Example — Binary Search:

T(n) = T(n/2) + O(1)

One recursive call on half the input, plus constant work to compute the midpoint and compare.

Example — Merge Sort:

T(n) = 2T(n/2) + O(n)

Two recursive calls on half the input, plus O(n) work to merge.

Example — Naive Fibonacci:

T(n) = T(n-1) + T(n-2) + O(1)

Two calls on subproblems of sizes n-1 and n-2.

Solving these by hand requires substitution or recursion trees. The Master Theorem gives you a direct formula for a specific common form.

The Master Theorem Form

The Master Theorem applies to recurrences of the form:

T(n) = aT(n/b) + f(n)

Where:

• a ≥ 1 — number of recursive subproblems
• b > 1 — factor by which the input is divided
• f(n) — cost of work done outside the recursive calls (splitting + combining)
• n/b — size of each subproblem (can be floor or ceiling — asymptotically equivalent)

The key quantity is n^{log_b a}, which represents the total work done by the leaf nodes of the recursion tree (the base cases). Whether the work at each level is dominated by the recursion or the combining step determines the answer.

Three Cases

Case 1: Recursion Dominates

Condition: f(n) = O(n^{log_b a - ε}) for some ε > 0

f(n) grows strictly slower than n^{log_b a}. The work at the leaves is the bottleneck.

Result: T(n) = Θ(n^{log_b a})

Example — Binary Tree Traversal:

T(n) = 2T(n/2) + O(1)

• a = 2, b = 2 → n^{log_2 2} = n¹ = n
• f(n) = O(1) = O(n^1-1) — grows slower than n

→ T(n) = Θ(n)

Intuition: We visit every node once (n nodes in a balanced binary tree), doing O(1) work each. The leaf count dominates.

Example — 8-way split with constant combine:

T(n) = 8T(n/2) + O(n²)

• a = 8, b = 2 → n^{log_2 8} = n³
• f(n) = O(n²) = O(n^3-1) — grows slower than n³

→ T(n) = Θ(n³)

Case 2: Equal Work at Every Level

Condition: f(n) = Θ(n^{log_b a} · logᵏ n) for some k ≥ 0

The most common subcase is k=0: f(n) = Θ(n^{log_b a}).

Result: T(n) = Θ(n^{log_b a} · log^k+1 n)

For k=0: T(n) = Θ(n^{log_b a} · log n)

Example — Merge Sort:

T(n) = 2T(n/2) + O(n)

• a = 2, b = 2 → n^{log_2 2} = n¹ = n
• f(n) = O(n) = Θ(n¹) — matches (k=0)

→ T(n) = Θ(n log n)

Intuition: There are log n levels of recursion. At each level, the total work across all subproblems is O(n). Multiplying: O(n log n).

Level 0:  [        n elements        ]  → O(n) work
Level 1:  [  n/2  ] [  n/2  ]          → O(n) work
Level 2:  [n/4][n/4][n/4][n/4]         → O(n) work
...
Level log n: n base cases              → O(n) work

log n levels × O(n) work = O(n log n)

Example — k=1 subcase:

T(n) = 2T(n/2) + O(n log n)

• a = 2, b = 2 → n^{log_2 2} = n
• f(n) = O(n log n) = Θ(n · log¹ n) — matches with k=1

→ T(n) = Θ(n log² n)

Case 3: Combining Dominates

Condition: f(n) = Ω(n^{log_b a + ε}) for some ε > 0, AND f satisfies the regularity condition: af(n/b) ≤ cf(n) for some c < 1

f(n) grows strictly faster than n^{log_b a}. The combining step is the bottleneck.

Result: T(n) = Θ(f(n))

Example — Binary Search:

T(n) = T(n/2) + O(1)

Wait — O(1) grows slower than n^{log_2 1} = n⁰ = 1. Actually n⁰ = 1 and f(n) = O(1) matches exactly — this is Case 2 with n⁰ = 1 and f(n) = Θ(1). The result is T(n) = Θ(log n).

Let's use a clearer Case 3 example:

Example — 1 subproblem of size n/2, quadratic combining:

T(n) = T(n/2) + O(n²)

• a = 1, b = 2 → n^{log_2 1} = n⁰ = 1
• f(n) = O(n²) = Ω(n^{0 + ε}) for any ε ≤ 2 — grows faster than 1

Regularity check: a · f(n/b) = 1 · (n/2)² = n²/4 ≤ (3/4) · n² ✓

→ T(n) = Θ(n²)

The single recursion into n/2 quickly becomes irrelevant. The n² combining work at the top level dominates everything.

Example — Strassen's Matrix Multiplication:

Standard matrix multiplication:

T(n) = 8T(n/2) + O(n²)   → a=8, b=2, n^(log_2 8) = n³
f(n) = O(n²) grows slower than n³ → Case 1 → T(n) = Θ(n³)

Strassen's algorithm reduces 8 multiplications to 7:

T(n) = 7T(n/2) + O(n²)   → a=7, b=2, n^(log_2 7) ≈ n^2.807
f(n) = O(n²) grows slower than n^2.807 → Case 1 → T(n) = Θ(n^2.807)

One fewer multiplication per recursion saves an asymptotic factor. This is why Strassen's is faster despite its complexity.

Summary Table

When the Master Theorem Does NOT Apply

The theorem has strict requirements. It fails when:

1. Subproblems are not equal size

T(n) = T(n/3) + T(2n/3) + O(n)   ← Quicksort worst/average, unbalanced split

The two subproblems are n/3 and 2n/3 — different sizes. Master Theorem doesn't apply. Use the Akra-Bazzi method or a recursion tree argument.

For this specific recurrence, the recursion tree has O(log n) levels (the larger branch, 2n/3, determines depth), each with O(n) work → T(n) = Θ(n log n).

2. f(n) is not a polynomial

T(n) = 2T(n/2) + n/log n

f(n) = n/log n does not fit the polynomial form n^c. Master Theorem doesn't apply.

3. Subproblem reduction is not by a constant factor

T(n) = T(n - 1) + O(1)   ← Reduces by 1, not a fraction

This is not of the form T(n/b). Solving directly: T(n) = n × O(1) = O(n).

T(n) = T(√n) + O(1)      ← Reduces by square root

Use variable substitution: let m = log n, so T(2ᵐ) = T(2^m/2) + 1. Let S(m) = T(2ᵐ). Then S(m) = S(m/2) + 1. Now Master Theorem applies: a=1, b=2, f=O(1), n^{log_2 1} = 1. Case 2 → S(m) = Θ(log m) = Θ(log log n).

4. The regularity condition fails in Case 3

Case 3 requires af(n/b) ≤ cf(n) for some c < 1. If f(n) oscillates or grows irregularly, this may not hold even if f(n) dominates asymptotically.

The Recursion Tree Method (When Master Theorem Fails)

Draw the tree explicitly. At each level, compute the total work. Sum across all levels.

Example: T(n) = T(n/3) + T(2n/3) + n

Level 0:           n                     → n
Level 1:       n/3   2n/3                → n
Level 2:   n/9 2n/9 2n/9 4n/9           → n
...

Each level sums to n. The deepest path is the 2n/3 branch: depth = log_(n) = O(log n). Total: O(n log n).

Quick Reference: Solving a Recurrence with Master Theorem

1. Identify a, b, and f(n) from T(n) = aT(n/b) + f(n)
2. Compute n^{log_b a}
3. Compare f(n) to n^{log_b a}:
   • f grows slower → Case 1 → answer is n^{log_b a}
   • f grows same → Case 2 → answer is n^{log_b a} × log n
   • f grows faster → Case 3 (check regularity) → answer is f(n)

Next: Arrays & Strings — the most fundamental data structure and the foundation of everything that follows.