Recurrence Relations & the Master Theorem

Phase 0, Weeks 2–3

Every recursive algorithm has a cost that depends on the cost of its sub-problems. Recurrence relations are the language for stating that cost precisely. Without them, you’re guessing at recursive complexity — and guesses are frequently wrong. This document gives you three tools: the Master Theorem for the fast path, substitution for verification, and recursion trees for intuition.

1. What a Recurrence Relation Is

A recurrence relation expresses T(n) — the time cost of an algorithm on input of size n — in terms of T on smaller inputs plus overhead.

General form for divide-and-conquer:

T(n) = a · T(n/b) + f(n)

Where:

  • a = number of recursive subproblems

  • n/b = size of each subproblem

  • f(n) = cost of work done outside the recursive calls (splitting, merging, etc.)

  • Base case: T(1) = O(1) (or some constant)

Why you need this: Looking at recursive code and eyeballing complexity is cargo-cult analysis. merge_sort calls itself twice. Is it O(n²)? O(n log n)? O(2ⁿ)? You cannot know without the recurrence.

2. The Master Theorem: Fast Path for Divide-and-Conquer

The Master Theorem solves recurrences of the form T(n) = aT(n/b) + f(n) where a ≥ 1, b > 1, f(n) is asymptotically positive.

The key comparison is between f(n) and n^(log_b a). Call this critical exponent c* = log_b(a).

Case 1: f(n) = O(n^(c-ε)) for some ε > 0* → The recursive calls dominate. Solution: T(n) = Θ(n^c)*

Intuition: The work at each level grows as you go deeper. Total is dominated by the bottom of the recursion tree.

Case 2: f(n) = Θ(n^c · log^k n) for some k ≥ 0* → Work is roughly equal at each level. Solution: T(n) = Θ(n^c · log^(k+1) n)* (Most common: k=0 → T(n) = Θ(n^c* · log n))

Intuition: Each level does the same amount of work, and there are log n levels.

Case 3: f(n) = Ω(n^(c+ε)) for some ε > 0, AND a·f(n/b) ≤ c·f(n) for large n* → The top-level work dominates. Solution: T(n) = Θ(f(n))

Intuition: The work at the root dominates. Recursive calls are comparatively cheap.

3. Worked Examples

Example A: Merge Sort

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

  • a = 2, b = 2, f(n) = n

  • c* = log₂(2) = 1

  • f(n) = n = n¹ = Θ(n^c*) → Case 2 (k=0)

  • Solution: T(n) = Θ(n log n) ✓

This is why merge sort is O(n log n). At each of the log n levels, you do O(n) work (the merge step). Total = n · log n.

Example C: Strassen’s Matrix Multiplication

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

  • a = 7, b = 2, f(n) = n²

  • c* = log₂(7) ≈ 2.807

  • f(n) = n² = O(n^(2.807 - ε)) → Case 1

  • Solution: T(n) = Θ(n^log₂7) ≈ Θ(n^2.807)

This is why Strassen is better than naive O(n³) matrix multiplication. By reducing 8 recursive calls to 7, the exponent drops from 3 to ~2.807 — a significant win at scale.

Example D: A Case 3 Example

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

  • a = 2, b = 4, f(n) = n

  • c* = log₄(2) = 0.5 → n^0.5 = √n

  • f(n) = n = Ω(n^(0.5 + ε)) → Check regularity: 2·f(n/4) = 2·(n/4) = n/2 ≤ (3/4)·n ✓

  • Case 3 → Solution: T(n) = Θ(n)

The top-level work (O(n)) dominates the recursive work on smaller inputs.

4. Substitution Method (Proof by Induction)

The substitution method: guess the form of the solution, then prove it by induction.

Example: Prove T(n) = 2T(n/2) + n is O(n log n).

Step 1: Guess. We guess T(n) ≤ c·n·log n for some constant c.

Step 2: Inductive hypothesis. Assume T(k) ≤ c·k·log k for all k < n. In particular, T(n/2) ≤ c·(n/2)·log(n/2).

Step 3: Substitution.

T(n) = 2T(n/2) + n
     ≤ 2 · [c·(n/2)·log(n/2)] + n       (by inductive hypothesis)
     = c·n·log(n/2) + n
     = c·n·(log n - log 2) + n
     = c·n·log n - c·n·log 2 + n
     = c·n·log n - c·n + n               (since log 2 = 1)
     = c·n·log n - (c-1)·n
     ≤ c·n·log n                         (for c ≥ 1, the last term is ≤ 0)

Step 4: Base case. T(1) = 1 ≤ c·1·log(1) = 0 — this fails! Adjust the base: use T(2) ≤ c·2·log 2 = 2c. Choose c ≥ 1. ✓

Conclusion: T(n) = O(n log n). ∎

The substitution method is more flexible than Master Theorem — it works for non-divide-and-conquer recurrences. But you must guess correctly first. The recursion tree method below helps you make good guesses.

5. Recursion Tree Method

Draw the recursion tree, compute work at each level, sum across levels.

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

Level 0:          n                         work: n
                /   \
Level 1:       n/2   n/2                    work: n/2 + n/2 = n
              / \   / \
Level 2:    n/4 n/4 n/4 n/4                 work: 4 × n/4 = n
            ...
Level log n: 1  1   1   ...   1             work: n × 1 = n
             └────────────────┘
                   n leaves

Each level does exactly n work. There are log n + 1 levels (from level 0 to level log n where problems become size 1).

Total: n × (log n + 1) = Θ(n log n) ✓

Second example: T(n) = 3T(n/4) + n²

Level 0:       n²                           work: n²
             / | \
Level 1:  (n/4)² × 3 = 3n²/16             work: 3n²/16
          / | \  / | \  / | \
Level 2:                                    work: 9n²/256
...

Ratio between levels: 3/16 < 1. This is a decreasing geometric series. The dominant term is the root.

Total ≈ n² × Σ (3/16)^i = n² × 1/(1 - 3/16) = n² × 16/13 = Θ(n²) — confirms Case 3.

6. Practice Problems

Problem 1. Solve: T(n) = 3T(n/3) + O(n)

Solution c* = log₃(3) = 1. f(n) = n = Θ(n¹). Case 2. T(n) = Θ(n log n).

Problem 2. Solve: T(n) = 9T(n/3) + O(n²)

Solution c* = log₃(9) = 2. f(n) = n². Case 2 (k=0). T(n) = Θ(n² log n).

Problem 3. Solve: T(n) = T(n-1) + O(1) [Note: NOT in Master Theorem form]

Solution Draw the tree: T(n) = T(n-1) + 1 = T(n-2) + 2 = ... = T(1) + (n-1) = O(n). This is linear recursion — a stack n deep, O(1) per frame. T(n) = O(n).

Problem 4. What is the complexity of the following?

def f(n):
    if n <= 1: return
    f(n//2)
    f(n//2)
    f(n//2)
    for i in range(n):
        print(i)
Solution T(n) = 3T(n/2) + O(n). c* = log₂(3) ≈ 1.585. f(n) = n = O(n^(1.585 - ε)). Case 1. T(n) = Θ(n^log₂3) ≈ Θ(n^1.585).

What Most Engineers Get Wrong

Eyeballing it. People look at a function with two recursive calls and say “O(2ⁿ)” or look at one recursive call and say “O(n)”. Both can be catastrophically wrong. The recurrence is the only reliable tool. Write T(n) = … before you analyze anything recursive.

Misidentifying the subproblem size. T(n) = T(n/2) + O(1) and T(n) = T(n-1) + O(1) look similar but are O(log n) and O(n) respectively. The difference is whether you halve or subtract. Always identify the actual subproblem size.

Forgetting the Master Theorem requires specific form. Master Theorem requires T(n) = aT(n/b) + f(n) with integer a ≥ 1, b > 1. It does NOT apply to T(n) = T(n-1) + f(n), T(n) = T(√n) + f(n), or T(n) = T(n/2) + T(n/3) + f(n). Use substitution or recursion trees for those.

Return to README.md · Next: 03_mathematical_thinking.md