Recurrence relations and the Master Theorem

Algorithms · Complexity analysis

Recurrence relations and the Master Theorem

Recurrences translate the structure of a recursive algorithm into an equation. The Master Theorem quickly solves many divide-and-conquer recurrences, provided that all of its hypotheses are actually satisfied.

Why recurrences appear

A recursive algorithm solves an instance using one or more smaller instances. Its running time is therefore the cost of the recursive calls plus the work performed outside them.

Binary search

$T (n) = T (n / 2) + Θ (1)$ : one half and constant local work.

Merge sort

$T (n) = 2 T (n / 2) + Θ (n)$ : two halves and linear merging.

Linear recursion

$T (n) = T (n - 1) + Θ (n)$ : the problem shrinks by one.

A base case is essential. For example,

T (1) = Θ (1)

. Without a stopping condition, the recurrence does not describe a terminating algorithm.

Reading a divide-and-conquer recurrence

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

$a$ — subproblems

The number of recursive calls produced by each instance. It must be at least 1.

$b$ — shrink factor

Each subproblem has size $n / b$ ; the theorem requires $b > 1$ .

$f (n)$ — local work

Splitting, combining and every operation performed outside the recursive calls.

The leaf cost of the recursion tree is governed by

a^{\log_{b} n} = n^{\log_{b} a}

This is why the Master Theorem compares $f (n)$ with $n^{\log_{b} a}$ .

Solution methods

Iteration

Repeatedly expand the recurrence down to the base case, then identify and sum the resulting series.

Recursion tree

Find the cost of each level, the number of levels and the leaf cost. This is especially useful for forming a hypothesis.

Substitution

Guess an asymptotic bound and prove it by induction, choosing constants and the base case carefully.

Master Theorem

Classify balanced recurrences of the form $a T (n / b) + f (n)$ .

A short expansion example

For $T (n) = T (n - 1) + n$ :

T (n) = T (1) + \sum_{i = 2}^{n} i = Θ (n^{2})

The Master Theorem does not apply because the size changes from $n$ to $n - 1$ , not to $n / b$ .

Master Theorem

Let

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

Compare $f (n)$ with $n^{c}$ . In cases 1 and 3, the gap must be polynomial.

Case	Comparison	Result	Intuition
1	$f (n) = O (n^{c - ε})$ , some $ε > 0$	$Θ (n^{c})$	Leaves dominate.
2	$f (n) = Θ (n^{c} \log^{k} n)$ , $k \geq 0$	$Θ (n^{c} \log^{k + 1} n)$	All levels contribute.
3	$f (n) = Ω (n^{c + ε})$ , some $ε > 0$	$Θ (f (n))$	The root dominates.

Case 3 also requires regularity: there must be a constant

q < 1

such that

a f (n / b) \leq q f (n)

for all sufficiently large

n

Practical procedure

Rewrite the recurrence as $a T (n / b) + f (n)$ .
Identify $a$ , $b$ and $f (n)$ .
Compute $c = \log_{b} a$ and $n^{c}$ .
Compare the growth of $f (n)$ and $n^{c}$ , checking for a polynomial gap.
For case 3, explicitly verify regularity.
State the result in $Θ$ notation.

Worked examples

Recurrence	Critical term	Case	Solution
$T (n) = T (n / 2) + 1$	$1$	2	$Θ (\log n)$
$T (n) = 2 T (n / 2) + n$	$n$	2	$Θ (n \log n)$
$T (n) = 8 T (n / 2) + n^{2}$	$n^{3}$	1	$Θ (n^{3})$
$T (n) = 7 T (n / 2) + n^{2}$	$n^{\log_{2} 7}$	1	$Θ (n^{2.807})$
$T (n) = 3 T (n / 4) + n \log n$	$n^{0.792}$	3	$Θ (n \log n)$

When the Master Theorem does not apply

Unequal subproblem sizes: $T (n) = T (n / 3) + T (2 n / 3) + n$ .
Subtractive shrinkage: $T (n) = T (n - 1) + n$ .
A nonconstant number of subproblems: for example $n T (n / 2)$ .
No polynomial gap: functions such as $n^{c} \log \log n$ do not fit the standard three cases.
Unverified regularity: case 3 needs more than just a larger $f (n)$ .

Use iteration, a recursion tree or substitution in these cases. The Akra–Bazzi theorem can handle more general divide-and-conquer recurrences.

Common mistakes

Applying the theorem without checking the required recurrence form.
Comparing $f (n)$ with $\log_{b} a$ instead of $n^{\log_{b} a}$ .
Using case 1 or 3 when the gap is only logarithmic.
Forgetting the extra logarithmic factor in case 2.
Omitting splitting or combining work from $f (n)$ .

Exercises with solutions

1. Leaf-dominated

Solve $T (n) = 4 T (n / 2) + n$ .

Show solution

The critical term is $n^{2}$ , which polynomially dominates $n$ . Case 1 gives $Θ (n^{2})$ .

2. Logarithmic factor

Solve $T (n) = 2 T (n / 2) + n \log n$ .

Show solution

Case 2 with $k = 1$ gives $Θ (n \log^{2} n)$ .

3. Root-dominated

Solve $T (n) = 2 T (n / 2) + n^{2}$ .

Show solution

The critical term is $n$ ; regularity holds because $2 f (n / 2) = n^{2} / 2$ . Case 3 gives $Θ (n^{2})$ .

4. Recognise the limit

Can the theorem solve $T (n) = T (n - 2) + 1$ ?

Show solution

No. The shrinkage is subtractive. Expansion takes about $n / 2$ constant-cost steps, so the result is $Θ (n)$ .

Checklist: identify the form, compute $n^{\log_{b} a}$ , compare it with $f (n)$ , and verify every hypothesis before selecting a case.

Why recurrences appear

Binary search

Merge sort

Linear recursion

Reading a divide-and-conquer recurrence

a — subproblems

b — shrink factor

f(n) — local work

Solution methods

Iteration

Recursion tree

Substitution

Master Theorem

A short expansion example

Master Theorem

Practical procedure

Worked examples

When the Master Theorem does not apply

Common mistakes

Exercises with solutions

1. Leaf-dominated

2. Logarithmic factor

3. Root-dominated

4. Recognise the limit

$a$ — subproblems

$b$ — shrink factor

$f (n)$ — local work