Recurrence Relations

March 2026 · 26 min read

Recursive algorithms don't have a simple loop to count. Instead, their running time is defined in terms of itself: $T(n) = 2T(n/2) + O(n)$. This is a recurrence relation. Solving it gives us the closed-form complexity.

Writing Recurrences from Code

Example: Merge Sort

void mergeSort(vector<int>& arr, int l, int r) {
    if (l >= r) return;                    // base case: O(1)
    int mid = (l + r) / 2;
    mergeSort(arr, l, mid);                 // T(n/2)
    mergeSort(arr, mid + 1, r);             // T(n/2)
    merge(arr, l, mid, r);                  // O(n)
}

Recurrence: $T(n) = 2T(n/2) + cn$, with $T(1) = O(1)$.

Example: Binary Search

int binarySearch(vector<int>& a, int lo, int hi, int t) {
    if (lo > hi) return -1;                // O(1)
    int mid = (lo + hi) / 2;               // O(1)
    if (a[mid] == t) return mid;            // O(1)
    if (a[mid] < t) return binarySearch(a, mid+1, hi, t);  // T(n/2)
    return binarySearch(a, lo, mid-1, t);                     // T(n/2)
}

Only one recursive call is made (the other branch is an if-else). Recurrence: $T(n) = T(n/2) + O(1)$.

The Master Theorem

The Master Theorem solves recurrences of the form:

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

where $a \geq 1$ (number of subproblems), $b > 1$ (factor by which input shrinks), and $f(n)$ is the non-recursive work.

Let $c_{\text{crit}} = \log_b a$. Compare $f(n)$ with $n^{c_{\text{crit}}}$:

Case 1: If $f(n) = O(n^{c_{\text{crit}} - \epsilon})$ for some $\epsilon > 0$ (recursion dominates): $$T(n) = \Theta(n^{c_{\text{crit}}})$$

Case 2: If $f(n) = \Theta(n^{c_{\text{crit}}} \cdot \log^k n)$ for $k \geq 0$ (balanced): $$T(n) = \Theta(n^{c_{\text{crit}}} \cdot \log^{k+1} n)$$

Case 3: If $f(n) = \Omega(n^{c_{\text{crit}} + \epsilon})$ for some $\epsilon > 0$ AND $af(n/b) \leq cf(n)$ for some $c < 1$ (combine dominates): $$T(n) = \Theta(f(n))$$

Example Applications

Recurrence	$a$	$b$	$c_{\text{crit}}$	$f(n)$	Case	Result
$T(n) = 2T(n/2) + n$	2	2	1	$n$	2 ($k$=0)	$\Theta(n \log n)$
$T(n) = T(n/2) + 1$	1	2	0	$1$	2 ($k$=0)	$\Theta(\log n)$
$T(n) = 4T(n/2) + n$	4	2	2	$n$	1	$\Theta(n^2)$
$T(n) = 2T(n/2) + n^2$	2	2	1	$n^2$	3	$\Theta(n^2)$
$T(n) = 3T(n/4) + n\log n$	3	4	$\approx 0.79$	$n\log n$	3	$\Theta(n \log n)$
$T(n) = 7T(n/2) + n^2$	7	2	$\approx 2.81$	$n^2$	1	$\Theta(n^{2.81})$

The last row is Strassen's algorithm for matrix multiplication. The Master Theorem immediately gives us $\Theta(n^{\log_2 7}) \approx \Theta(n^{2.807})$, beating the naive $O(n^3)$.

The Recursion Tree Method

Draw the recursive calls as a tree. At each level, compute the total work. Sum across all levels.

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

Level 0:  cn                            (1 node, work = cn)
Level 1:  c(n/2) + c(n/2)              (2 nodes, work = cn)
Level 2:  c(n/4) + c(n/4) + ...        (4 nodes, work = cn)
  ...
Level k:  2^k nodes, each c(n/2^k)     (work = cn per level)
  ...
Level log n: n nodes, each c(1)         (work = cn)

There are $\log_2 n + 1$ levels, each with $cn$ work:

$$T(n) = cn \cdot (\log_2 n + 1) = \Theta(n \log n)$$

Example: $T(n) = 3T(n/4) + cn^2$

Level 0:  cn²                           (work = cn²)
Level 1:  3 × c(n/4)² = 3cn²/16        (work = 3cn²/16)
Level 2:  9 × c(n/16)² = 9cn²/256      (work = 9cn²/256)
Level k:  3^k × c(n/4^k)²              (work = cn² × (3/16)^k)

The work decreases geometrically by factor $3/16$ at each level. The root dominates:

$$T(n) = cn^2 \sum_{k=0}^{\log_4 n} \left(\frac{3}{16}\right)^k < cn^2 \cdot \frac{1}{1 - 3/16} = \frac{16cn^2}{13} = O(n^2)$$

The Substitution Method

Step 1: Guess the answer (from a recursion tree, intuition, or pattern matching).

Step 2: Prove it correct by induction.

Example: Prove $T(n) = 2T(n/2) + n = O(n \log n)$

Guess: $T(n) \leq cn \log n$ for some constant $c$.

Inductive step: Assume $T(k) \leq ck \log k$ for all $k < n$.

$$T(n) = 2T(n/2) + n \leq 2 \cdot c(n/2)\log(n/2) + n$$ $$= cn(\log n - 1) + n = cn\log n - cn + n$$ $$= cn\log n - (c - 1)n \leq cn\log n \quad \text{when } c \geq 1 \quad \checkmark$$

Example: Prove $T(n) = T(n-1) + n = O(n^2)$

Guess: $T(n) \leq cn^2$.

$$T(n) = T(n-1) + n \leq c(n-1)^2 + n = cn^2 - 2cn + c + n$$ $$= cn^2 - (2c - 1)n + c \leq cn^2 \quad \text{when } 2c - 1 > 0, \text{ i.e., } c > 1/2 \quad \checkmark$$

Common Recurrence Cheat Sheet

Recurrence	Solution	Algorithm
$T(n) = T(n/2) + O(1)$	$O(\log n)$	Binary search
$T(n) = T(n-1) + O(1)$	$O(n)$	Linear scan / factorial
$T(n) = 2T(n/2) + O(n)$	$O(n \log n)$	Merge sort
$T(n) = 2T(n/2) + O(1)$	$O(n)$	Tree traversal
$T(n) = T(n-1) + O(n)$	$O(n^2)$	Selection sort
$T(n) = 2T(n-1) + O(1)$	$O(2^n)$	Towers of Hanoi
$T(n) = T(n/2) + O(n)$	$O(n)$	Median of medians
$T(n) = T(n/3) + T(2n/3) + O(n)$	$O(n \log n)$	Unbalanced quicksort

Beyond Master Theorem: Akra-Bazzi

The Master Theorem requires equal-sized subproblems ($n/b$). For unequal splits like quicksort's $T(n) = T(n/3) + T(2n/3) + O(n)$, use the Akra-Bazzi method:

For $T(n) = \sum_{i=1}^{k} a_i T(b_i n) + g(n)$, find $p$ such that $\sum a_i b_i^p = 1$. Then:

$$T(n) = \Theta\left(n^p\left(1 + \int_1^n \frac{g(u)}{u^{p+1}} du\right)\right)$$

For quicksort with $T(n) = T(n/3) + T(2n/3) + cn$: solve $(1/3)^p + (2/3)^p = 1$, giving $p = 1$. Then:

$$T(n) = \Theta\left(n\left(1 + \int_1^n \frac{cu}{u^2} du\right)\right) = \Theta(n(1 + c\ln n)) = \Theta(n \log n)$$

Summary

Recursive algorithms produce recurrence relations: $T(n)$ in terms of $T(\text{smaller})$.
The Master Theorem handles $T(n) = aT(n/b) + f(n)$: compare $f(n)$ to $n^{\log_b a}$.
The recursion tree method visualizes total work per level and sums them.
The substitution method guesses and proves via induction.
Akra-Bazzi generalizes to unequal subproblems.