Recurrences & Master Theorem

Master the analysis of divide-and-conquer algorithms through recursion trees, the Master Theorem, and geometric series

Analyzing Recursive Algorithms

Divide-and-conquer algorithms break problems into subproblems, solve them recursively, then combine results. But how do we determine their complexity? The answer lies in understanding recurrence relations.

The Master Theorem provides a powerful shortcut for recurrences of the form T(n) = aT(n/b) + f(n). By comparing the work at different levels of the recursion tree, we can immediately determine if the algorithm is O(n), O(n log n), O(n²), or something else entirely.

In this section, you'll visualize recursion trees, discover why the Master Theorem works through geometric series, and extend to more complex recurrences with the Akra-Bazzi method and characteristic equations.

Demo 1: Recursion Tree Visualization

Every divide-and-conquer recurrence T(n) = aT(n/b) + f(n) corresponds to a recursion tree. At each level, the problem splits into a subproblems of size n/b. Watch how work distributes across levels!

a (subproblems): 2

b (size factor): 2

d (work exponent): 1

n (input size): 16

T(n) = 2T(n/2) + Θ(n)log₂(2) = 1.00

Work by Level

Level	# Problems	Size	Work/Problem	Total Work
0	2^0 = 1	16	16.0	16.0
1	2^1 = 2	8	8.0	16.0
2	2^2 = 4	4	4.0	16.0
3	2^3 = 8	2	2.0	16.0
4	2^4 = 16	1	1.0	16.0

Tree Depth

⌈log₂(16)⌉

Leaf Nodes

2^4

Total Work

Σ levels

Demo 2: The Master Theorem

The Master Theorem has three cases based on comparing f(n) to n^log_b(a). This determines whether work is dominated by leaves (Case 1), balanced across levels (Case 2), or dominated by the root (Case 3).

a (subproblems): 2

b (size factor): 2

d (work exponent): 1

T(n) = 2T(n/2) + Θ(n¹)

log₂(2) = 1.000

d = 1

ratio a/b^d = 1.000

Case 2: Θ(n^ log n)

f(n) = Θ(n^1) matches n^(log_2(2)) = n^1.00. Work is evenly distributed across all log_2(n) levels.

Case 1: Leaf-Dominated

d < log_b(a)

Work increases down the tree.
T(n) = Θ(n^log_b(a))

Case 2: Balanced

d = log_b(a)

Same work at each level.
T(n) = Θ(n^d log n)

Work evenly distributed!

Case 3: Root-Dominated

d > log_b(a)

Work decreases down the tree.
T(n) = Θ(n^d)

Parameter Space (for b = 2)

White line: d = log₂(a) — the boundary between cases

Common Algorithms

Demo 3: Why Three Cases? Geometric Series

The total work is a geometric series with ratio r = a/b^d. When r < 1, the series converges (root dominates). When r > 1, it diverges (leaves dominate). When r = 1, all terms are equal (balanced).

The Key Insight

Total work T(n) is a geometric series:

T(n) = n^d × (1 + r + r² + ... + r^L)

where r = a/b^d is the ratio between consecutive levels, and L = log_b(n) is the tree depth.

a: 2

b: 2

d: 1

Levels: 6

Ratio

r = 1.000

a / b^d = 2 / 2¹

→

Constant (Balanced)

Sum is O(L) = O(log n)

Geometric Series Terms

r⁰

1.00

r¹

1.00

r²

1.00

r³

1.00

r⁴

1.00

r⁵

1.00

r⁶

1.00

Work at each level (relative to level 0)

1 + 1.00 + 1.00 + ... + 1.00 = 7.00

r > 1

Series diverges

Dominated by largest term (leaves)

T(n) = Θ(n^log_ba)

r = 1

Series has L+1 equal terms

Each level contributes equally

T(n) = Θ(n^d log n)

r < 1

Series converges

Dominated by first term (root)

T(n) = Θ(n^d)

Why does r = a/b^d determine everything?

At level k, there are a^k subproblems, each of size n/b^k.

Work at level k = a^k × (n/b^k)^d = n^d × (a/b^d)^k = n^d × r^k

Total work = n^d × Σ_k=0..L r^k

This is a geometric series! Its sum depends on whether r < 1, r = 1, or r > 1.

Demo 4: Beyond Master Theorem (Akra-Bazzi)

What if subproblems have different sizes? The Akra-Bazzi method handles T(n) = T(n/2) + T(n/3) + f(n) by finding p where the sum of a_i/b_i^p equals 1.

Beyond the Master Theorem

The Akra-Bazzi method solves recurrences with multiple, differently-sized subproblems:

T(n) = Σ a_i · T(n/b_i) + f(n)

Find p where Σ a_i/b_i^p = 1, then compare f(n) to n^p.

Subproblems

Term 1:

a₁:

b₁:

→ 1 × T(n/2)

Term 2:

a₂:

b₂:

→ 1 × T(n/3)

f(n):d:Θ(n)

T(n) = 1T(n/2) + 1T(n/3) + Θ(n¹)

Finding the Critical Exponent p

Σ a_i/b_i^p = 1/2^p + 1/3^p = 1

Solution

p = 0.788

Verification

Σ = 1.0000 ≈ 1

1/2^0.79

0.579

1/3^0.79

0.421

Complexity

Θ(n^1)

Divide/combine work dominates (d = 1, p = 0.79)

Comparison with Master Theorem

The Master Theorem is a special case of Akra-Bazzi where all subproblems have the same size: T(n) = aT(n/b) + f(n).

In this case, finding p is simple: a/b^p = 1 → p = log_b(a).

Akra-Bazzi handles more general recurrences where subproblems may have different sizes, like T(n) = T(n/2) + T(n/3) + n.

Demo 5: Linear Recurrences & Characteristic Equations

For recurrences like Fibonacci (T(n) = T(n-1) + T(n-2)), the characteristic equation method finds closed-form solutions. The roots determine exponential growth rates like the golden ratio.

Characteristic Equation Method

For linear homogeneous recurrences, the closed-form solution comes from solving a polynomial equation. The roots determine the growth rate.

Order:

Recurrence: T(n) =

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

Initial values:

T(0) =

T(1) =

Characteristic Equation

x² = 1x + 1

x² - 1x - 1 = 0

Root r₁

1.6180

Root r₂

-0.6180

Golden ratio: φ = (1 + √5)/2 ≈ 1.6180

Closed form: T(n) = c₁·r₁ⁿ + c₂·r₂ⁿ

Sequence Terms

Terms:15

n=0

n=1

n=2

n=3

n=4

n=5

n=6

n=7

n=8

n=9

n=10

n=11

n=12

144

n=13

233

n=14

377

Growth Analysis

Approximate Ratio

1.6216

T(n)/T(n-1) as n→∞

Growth Rate

Θ(1.62ⁿ)

Exponential in n

Ratio Convergence

n=1→ 1.6216n=14

Recurrence Analysis Mastered!

You now have a complete toolkit for analyzing recursive algorithms:

Recursion trees show how work distributes across levels
Master Theorem quickly solves T(n) = aT(n/b) + f(n)
Geometric series explain why there are exactly three cases
Akra-Bazzi extends to unequal subproblem sizes
Characteristic equations solve linear recurrences like Fibonacci

Next: We'll explore information-theoretic lower bounds, proving that comparison-based sorting must be Ω(n log n) using decision trees and entropy.