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 split a problem, solve the pieces, and combine the results. A recurrence relation like T(n) = aT(n/b) + f(n) captures their cost, and the demos below show how to solve one.

Recursion Tree Visualization

Pick a preset like Merge Sort or Strassen, or set a, b, and d yourself. Watch where the work piles up: at the root, at the leaves, or evenly across the 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

Go deeper: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!

The Master Theorem

Pick an example or set a, b, and d, and see which of the three cases applies. Each case comes from comparing f(n) to n^log_b(a).

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

Go deeper:The Master Theorem

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.

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).

Why Three Cases? Geometric Series

Adjust a, b, and d and watch the work per level form a geometric series with ratio r = a/b^d. Notice what changes as r crosses 1.

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.

Go deeper: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).

Beyond Master Theorem (Akra-Bazzi)

Try the T(n/2) + T(n/3) preset, or add subproblems of your own sizes. The demo finds the exponent p that sets the growth rate.

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.

Go deeper: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.

Linear Recurrences & Characteristic Equations

Pick Fibonacci or another preset and look at the roots of its characteristic equation. The largest root sets the growth rate — for Fibonacci, 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

Go deeper: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.

Key Takeaways

Recursion trees show how work distributes across levels
Master Theorem solves T(n) = aT(n/b) + f(n); a geometric series explains its three cases
Akra-Bazzi extends to unequal subproblem sizes
Characteristic equations solve linear recurrences like Fibonacci

Spot a mistake or have an idea?