Recurrence Relations and the Master Theorem
Two calls, two very different costs
Merge sort calls itself twice, on the two halves of its input. Naive Fibonacci calls itself twice too, on n − 1 and n − 2. To sort 2²⁰ values, about a million, merge sort moves values 20,971,520 times; to compute Fibonacci of 50, the naive version makes 40,730,022,147 calls. Counting the calls on our judge: merge sort's work went from 10,240 to 22,528 when n doubled from 1,024 to 2,048, while Fibonacci's calls went from 21,891 to 35,421 when n grew by just one, from 20 to 21.
A recursive function's cost isn't in a loop you can count. It's in an equation: the cost for n, written in terms of the cost of the smaller calls it makes. That equation is a recurrence relation. This lesson writes the recurrence from the code, solves it by summing the levels of its recursion tree, shows the Master Theorem, which reads the answer off for the common divide-and-conquer shape, and the recurrences it doesn't cover.
Writing the recurrence
Read a recursive function in two parts: the calls it makes, and the work it does outside them. Write T(n) for its cost on an input of size n:
- Binary search makes one call on half the range and does O(1) besides: T(n) = T(n/2) + 1.
- Merge sort makes two calls on halves and merges in O(n): T(n) = 2T(n/2) + n.
- Visiting a balanced tree makes two calls on the halves and does O(1) at each node: T(n) = 2T(n/2) + 1.
- Naive Fibonacci makes calls on n − 1 and n − 2: T(n) = T(n − 1) + T(n − 2) + 1.
The divide-and-conquer ones share the shape T(n) = a·T(n/b) + f(n): a calls, each on 1/b of the input, and f(n) work outside them. Each function below counts its own work at three sizes: 1,024, 2,048 and 4,096 values; full trees of 1,023, 2,047 and 4,095 nodes; and Fibonacci of 20, 21 and 22:
long long searchSteps(int n) { // binary search for a value bigger than all n: one call per halving
if (n == 0) return 1;
return 1 + searchSteps(n / 2);
}
long long mergeSteps(int n) { // merge sort's work: each merge moves every value of its range once
if (n <= 1) return 0;
int half = n / 2;
return mergeSteps(half) + mergeSteps(n - half) + n;
}
long long treeCalls(int n) { // visit a balanced tree of n nodes: a call per node and per empty child
if (n == 0) return 1;
int left = (n - 1) / 2;
return 1 + treeCalls(left) + treeCalls(n - 1 - left);
}
long long fibCalls(int n) { // naive Fibonacci: fib(n) calls fib(n - 1) and fib(n - 2)
if (n <= 1) return 1;
return 1 + fibCalls(n - 1) + fibCalls(n - 2);
}
// searchSteps [12, 13, 14]
// mergeSteps [10240, 22528, 49152]
// treeCalls [2047, 4095, 8191]
// fibCalls [21891, 35421, 57313]def search_steps(n): # binary search for a value bigger than all n: one call per halving
if n == 0:
return 1
return 1 + search_steps(n // 2)
def merge_steps(n): # merge sort's work: each merge moves every value of its range once
if n <= 1:
return 0
half = n // 2
return merge_steps(half) + merge_steps(n - half) + n
def tree_calls(n): # visit a balanced tree of n nodes: a call per node and per empty child
if n == 0:
return 1
left = (n - 1) // 2
return 1 + tree_calls(left) + tree_calls(n - 1 - left)
def fib_calls(n): # naive Fibonacci: fib(n) calls fib(n - 1) and fib(n - 2)
if n <= 1:
return 1
return 1 + fib_calls(n - 1) + fib_calls(n - 2)
# search_steps [12, 13, 14]
# merge_steps [10240, 22528, 49152]
# tree_calls [2047, 4095, 8191]
# fib_calls [21891, 35421, 57313]static long searchSteps(int n) { // binary search for a value bigger than all n: one call per halving
if (n == 0) return 1;
return 1 + searchSteps(n / 2);
}
static long mergeSteps(int n) { // merge sort's work: each merge moves every value of its range once
if (n <= 1) return 0;
int half = n / 2;
return mergeSteps(half) + mergeSteps(n - half) + n;
}
static long treeCalls(int n) { // visit a balanced tree of n nodes: a call per node and per empty child
if (n == 0) return 1;
int left = (n - 1) / 2;
return 1 + treeCalls(left) + treeCalls(n - 1 - left);
}
static long fibCalls(int n) { // naive Fibonacci: fib(n) calls fib(n - 1) and fib(n - 2)
if (n <= 1) return 1;
return 1 + fibCalls(n - 1) + fibCalls(n - 2);
}
// searchSteps [12, 13, 14]
// mergeSteps [10240, 22528, 49152]
// treeCalls [2047, 4095, 8191]
// fibCalls [21891, 35421, 57313]function searchSteps(n) { // binary search for a value bigger than all n: one call per halving
if (n === 0) return 1;
return 1 + searchSteps(Math.floor(n / 2));
}
function mergeSteps(n) { // merge sort's work: each merge moves every value of its range once
if (n <= 1) return 0;
const half = Math.floor(n / 2);
return mergeSteps(half) + mergeSteps(n - half) + n;
}
function treeCalls(n) { // visit a balanced tree of n nodes: a call per node and per empty child
if (n === 0) return 1;
const left = Math.floor((n - 1) / 2);
return 1 + treeCalls(left) + treeCalls(n - 1 - left);
}
function fibCalls(n) { // naive Fibonacci: fib(n) calls fib(n - 1) and fib(n - 2)
if (n <= 1) return 1;
return 1 + fibCalls(n - 1) + fibCalls(n - 2);
}
// searchSteps [12, 13, 14]
// mergeSteps [10240, 22528, 49152]
// treeCalls [2047, 4095, 8191]
// fibCalls [21891, 35421, 57313]Binary search made 12, 13 and 14 calls: one more per doubling, O(log n). Merge sort's work was n log₂ n exactly, 10,240 for 1,024 values, ×2.20 per doubling: O(n log n). The tree took 2n + 1 calls, one per node and per empty child, ×2: O(n). And Fibonacci's calls grew ×1.618 each time n grew by one, the golden ratio, so they grow like 1.618ⁿ: exponential.
Sum the levels of the tree
Draw the calls as a tree, the first call at the top and its calls below it, and add up the work level by level. For merge sort on n values, level k has 2ᵏ calls, each on n/2ᵏ values, so each level merges 2ᵏ × n/2ᵏ = n values. The sizes halve until they reach 1, which takes log₂ n levels. n work on each of log n levels is n log n.
The same sum tells the other recurrences apart, by how a level's total compares with the level above:
- Each level the same (merge sort, and binary search's 1 per level): the total is one level's work times log n.
- Each level bigger (the tree visit: 1, 2, 4, … calls, each O(1)): the bottom level, with about n calls, outweighs everything above it, O(n).
- Each level smaller (T(n) = T(n/2) + n: n, n/2, n/4, …): the top level outweighs the rest, O(n).
Sum the Levels. Pick a recurrence and grow its tree one level at a time. Before each level appears, say whether its total will be more than, the same as, or less than the level above; at the end, say which part of the tree holds most of the work.
Checking the answer: substitution. The tree's sum gives a guess; putting the guess back into the recurrence proves it. For merge sort with T(1) = 1, the tree says T(n) = n log₂ n + n. Substitute it for T(n/2) on the right: 2((n/2)(log₂ n − 1) + n/2) + n = n log₂ n − n + n + n = n log₂ n + n, the guess again, and at n = 1 it gives 1 · 0 + 1 = 1. So the guess is exact for every power of 2: T(1,024) = 1,024 × 10 + 1,024 = 11,264, the value our judge computed. When the guess is a bound, like T(n) ≤ c · n log n, the same substitution, applied step by step from the base case up (induction), proves the bound.
The Master Theorem
For T(n) = a·T(n/b) + f(n), the bottom level has about n^(log_b a) calls: a calls per level, over log_b n levels. The Master Theorem compares that with f(n), the work at the top:
- The leaves win when f(n) grows polynomially slower than n^(log_b a): T(n) = Θ(n^(log_b a)).
- Every level ties when f(n) = Θ(n^(log_b a)): T(n) = Θ(n^(log_b a) · log n).
- The root wins when f(n) grows polynomially faster, and a·f(n/b) ≤ c·f(n) for some c < 1 (each level does less than the one above it): T(n) = Θ(f(n)).
"Polynomially" means by a power of n: n against n^1.58 differ by n^0.58. A log factor isn't enough for case 1 or 3; the extended tie below covers f(n) that differs from n^(log_b a) only by logs.
Each row below was computed exactly on our judge, T(1) = 1, at n = 2¹⁰, 2¹¹ and 2¹²; the last column is what doubling n did to T(n):
| Recurrence | n^(log_b a) against f(n) | Answer | When n doubles |
|---|---|---|---|
| T(n) = 2T(n/2) + 1 | n against 1: the leaves | Θ(n) | ×2.00 |
| T(n) = 3T(n/2) + n | n^1.58 against n: the leaves | Θ(n^1.58) | ×3.01 |
| T(n) = T(n/2) + 1 | 1 against 1: every level | Θ(log n) | +1 |
| T(n) = 2T(n/2) + n | n against n: every level | Θ(n log n) | ×2.17 |
| T(n) = 4T(n/2) + n² | n² against n²: every level | Θ(n² log n) | ×4.33 |
| T(n) = T(n/2) + n | 1 against n: the root | Θ(n) | ×2.00 |
| T(n) = 2T(n/2) + n² | n against n²: the root | Θ(n²) | ×4.00 |
Binary search is T(n/2) + 1: n^(log₂ 1) = n⁰ = 1, the same as f(n), a tie, so Θ(log n). Merge sort ties at n: Θ(n log n). Three half-size calls with linear work, the shape of Karatsuba's multiplication, make the leaves win: n^(log₂ 3) ≈ n^1.58, and doubling n tripled T(n).
The extended tie. If f(n) is n^(log_b a) times a power of log n, the answer gains one more log: T(n) = 2T(n/2) + n log n is Θ(n log² n). Computed, it went ×2.358 from 2¹¹ to 2¹², close to the 2.380 that n log² n gives. Some books leave this case out and say the theorem doesn't apply.
When the Master Theorem doesn't fit
The input shrinks by subtraction. A call on n − 1 isn't n/b for any b. Unroll it instead: write T(n − 1) in terms of T(n − 2), and so on to the base case, and add up what's left:
long long countdownCalls(int n) { // T(n) = T(n - 1) + 1
if (n == 0) return 1;
return 1 + countdownCalls(n - 1);
}
long long peelSteps(int n) { // T(n) = T(n - 1) + n: scan what's left, then recurse on one fewer
if (n == 0) return 0;
return n + peelSteps(n - 1);
}
long long hanoiMoves(int n) { // T(n) = 2T(n - 1) + 1: move n - 1 off, move one, move n - 1 back on
if (n == 0) return 0;
return 2 * hanoiMoves(n - 1) + 1;
}
// countdownCalls [201, 401, 801]
// peelSteps [20100, 80200, 320400]
// hanoiMoves [1048575, 2097151, 4194303]def countdown_calls(n): # T(n) = T(n - 1) + 1
if n == 0:
return 1
return 1 + countdown_calls(n - 1)
def peel_steps(n): # T(n) = T(n - 1) + n: scan what's left, then recurse on one fewer
if n == 0:
return 0
return n + peel_steps(n - 1)
def hanoi_moves(n): # T(n) = 2T(n - 1) + 1: move n - 1 off, move one, move n - 1 back on
if n == 0:
return 0
return 2 * hanoi_moves(n - 1) + 1
# countdown_calls [201, 401, 801]
# peel_steps [20100, 80200, 320400]
# hanoi_moves [1048575, 2097151, 4194303]static long countdownCalls(int n) { // T(n) = T(n - 1) + 1
if (n == 0) return 1;
return 1 + countdownCalls(n - 1);
}
static long peelSteps(int n) { // T(n) = T(n - 1) + n: scan what's left, then recurse on one fewer
if (n == 0) return 0;
return n + peelSteps(n - 1);
}
static long hanoiMoves(int n) { // T(n) = 2T(n - 1) + 1: move n - 1 off, move one, move n - 1 back on
if (n == 0) return 0;
return 2 * hanoiMoves(n - 1) + 1;
}
// countdownCalls [201, 401, 801]
// peelSteps [20100, 80200, 320400]
// hanoiMoves [1048575, 2097151, 4194303]function countdownCalls(n) { // T(n) = T(n - 1) + 1
if (n === 0) return 1;
return 1 + countdownCalls(n - 1);
}
function peelSteps(n) { // T(n) = T(n - 1) + n: scan what's left, then recurse on one fewer
if (n === 0) return 0;
return n + peelSteps(n - 1);
}
function hanoiMoves(n) { // T(n) = 2T(n - 1) + 1: move n - 1 off, move one, move n - 1 back on
if (n === 0) return 0;
return 2 * hanoiMoves(n - 1) + 1;
}
// countdownCalls [201, 401, 801]
// peelSteps [20100, 80200, 320400]
// hanoiMoves [1048575, 2097151, 4194303]- T(n) = T(n − 1) + 1 unrolls to n + 1 calls: 201 for n = 200. O(n), and O(n) deep: that's the recursion Introduction to Recursion measured against each language's stack limit.
- T(n) = T(n − 1) + n unrolls to n + (n − 1) + … + 1 = n(n + 1)/2: 20,100 for n = 200, ×4 per doubling. O(n²): selection sort written recursively has this shape, and so has quick sort on sorted input.
- T(n) = 2T(n − 1) + 1 doubles with every step: 1,048,575 moves for the Towers of Hanoi with 20 discs, 2ⁿ − 1. O(2ⁿ).
Uneven splits. T(n) = T(n/3) + T(2n/3) + n splits unevenly, so a and b don't exist. Its tree still has at most n work per level, and the longest path, the 2/3 side, is log₃/₂ n levels deep, so it's O(n log n). Computed on our judge for n = 1,000 to 1,000,000, T(n) divided by n log₂ n stayed between 1.10 and 1.12.
Fibonacci, T(n) = T(n − 1) + T(n − 2) + 1, is exponential: its calls grew by the golden ratio, 1.618, each step. Remembering each fib(k) once computed means each is worked out once, O(n) in all; that's dynamic programming, and the Dynamic Programming section starts there.
Space is the deepest chain
A recursion's extra memory is the deepest chain of calls waiting on the stack at once, not the total number of calls, because a call's frame is gone once it returns. Merge sort makes 2n − 1 calls but is only log₂ n deep, so its stack is O(log n), plus the O(n) buffer it merges into. Binary search is O(log n) deep. Naive Fibonacci makes exponentially many calls but is only n deep, O(n). A recursion on n − 1 is n deep, and so is quick sort on sorted input with a fixed pivot (Best, Worst and Average Case measured it stopping Python at 1,000).
Mistakes that cost an interview
"Two recursive calls, so O(2ⁿ)." Only when each call shrinks the input by a constant. Two calls on halves make about 2n calls in all, not 2ⁿ: the tree visit above.
Binary search on slices. Passing a copy of the half you keep, instead of two indexes, makes each call copy n/2, n/4, … values: T(n) = T(n/2) + n, which is O(n), not O(log n):
#include <bits/stdc++.h>
using namespace std;
bool searchSlices(const vector<int>& nums, int target, long long& copied) { // recurses on a copy of the half
if (nums.empty()) return false;
size_t mid = nums.size() / 2;
if (nums[mid] == target) return true;
vector<int> half = nums[mid] < target ? vector<int>(nums.begin() + mid + 1, nums.end())
: vector<int>(nums.begin(), nums.begin() + mid);
copied += half.size();
return searchSlices(half, target, copied);
}
bool searchRange(const vector<int>& nums, int target, int lo, int hi) { // the same vector, two indexes
if (lo > hi) return false;
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return true;
if (nums[mid] < target) return searchRange(nums, target, mid + 1, hi);
return searchRange(nums, target, lo, mid - 1);
}
int main() {
for (int n : {1000000, 2000000, 4000000}) {
vector<int> nums(n);
iota(nums.begin(), nums.end(), 0);
long long copied = 0;
searchSlices(nums, n, copied); // a target bigger than all: the longest search
printf("n = %d: slices copied %lld values; indexes copied 0\n", n, copied);
if (searchRange(nums, n, 0, n - 1)) puts("?");
}
}
// n = 1000000: slices copied 999974 values; indexes copied 0
// n = 2000000: slices copied 1999973 values; indexes copied 0
// n = 4000000: slices copied 3999972 values; indexes copied 0def search_slices(nums, target, copied): # recurses on a copy of the half it keeps
if not nums:
return False
mid = len(nums) // 2
if nums[mid] == target:
return True
half = nums[mid + 1:] if nums[mid] < target else nums[:mid]
copied[0] += len(half)
return search_slices(half, target, copied)
def search_range(nums, target, lo, hi): # recurses on the same list, between two indexes
if lo > hi:
return False
mid = (lo + hi) // 2
if nums[mid] == target:
return True
if nums[mid] < target:
return search_range(nums, target, mid + 1, hi)
return search_range(nums, target, lo, mid - 1)
for n in (1000000, 2000000, 4000000):
nums = list(range(n))
copied = [0]
search_slices(nums, n, copied) # a target bigger than all: the longest search
print(f"n = {n}: slices copied {copied[0]} values; indexes copied 0")
assert not search_range(nums, n, 0, n - 1)
# n = 1000000: slices copied 999974 values; indexes copied 0
# n = 2000000: slices copied 1999973 values; indexes copied 0
# n = 4000000: slices copied 3999972 values; indexes copied 0import java.util.*;
public class Main {
static boolean searchSlices(int[] nums, int target, long[] copied) { // recurses on a copy of the half
if (nums.length == 0) return false;
int mid = nums.length / 2;
if (nums[mid] == target) return true;
int[] half = nums[mid] < target ? Arrays.copyOfRange(nums, mid + 1, nums.length)
: Arrays.copyOfRange(nums, 0, mid);
copied[0] += half.length;
return searchSlices(half, target, copied);
}
static boolean searchRange(int[] nums, int target, int lo, int hi) { // the same array, two indexes
if (lo > hi) return false;
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) return true;
if (nums[mid] < target) return searchRange(nums, target, mid + 1, hi);
return searchRange(nums, target, lo, mid - 1);
}
public static void main(String[] args) {
for (int n : new int[]{1000000, 2000000, 4000000}) {
int[] nums = new int[n];
for (int i = 0; i < n; i++) nums[i] = i;
long[] copied = {0};
searchSlices(nums, n, copied); // a target bigger than all: the longest search
System.out.printf("n = %d: slices copied %d values; indexes copied 0%n", n, copied[0]);
if (searchRange(nums, n, 0, n - 1)) System.out.println("?");
}
}
}
// n = 1000000: slices copied 999974 values; indexes copied 0
// n = 2000000: slices copied 1999973 values; indexes copied 0
// n = 4000000: slices copied 3999972 values; indexes copied 0function searchSlices(nums, target, copied) { // recurses on a copy of the half it keeps
if (nums.length === 0) return false;
const mid = Math.floor(nums.length / 2);
if (nums[mid] === target) return true;
const half = nums[mid] < target ? nums.slice(mid + 1) : nums.slice(0, mid);
copied[0] += half.length;
return searchSlices(half, target, copied);
}
function searchRange(nums, target, lo, hi) { // the same array, between two indexes
if (lo > hi) return false;
const mid = Math.floor((lo + hi) / 2);
if (nums[mid] === target) return true;
if (nums[mid] < target) return searchRange(nums, target, mid + 1, hi);
return searchRange(nums, target, lo, mid - 1);
}
for (const n of [1000000, 2000000, 4000000]) {
const nums = Array.from({ length: n }, (_, i) => i);
const copied = [0];
searchSlices(nums, n, copied); // a target bigger than all: the longest search
console.log(`n = ${n}: slices copied ${copied[0]} values; indexes copied 0`);
if (searchRange(nums, n, 0, n - 1)) console.log("?");
}
// n = 1000000: slices copied 999974 values; indexes copied 0
// n = 2000000: slices copied 1999973 values; indexes copied 0
// n = 4000000: slices copied 3999972 values; indexes copied 0Searching a million values copied 999,974 of them, and the copy doubled when n did: O(n), as slow as checking every value. The index version copied nothing. Python's nums[mid + 1:], JavaScript's slice, Java's Arrays.copyOfRange and building a new vector all copy.
Counting the calls and forgetting the work in each. Merge sort makes O(n) calls, and its cost is O(n log n) because each level of calls merges n values.
Using the Master Theorem on T(n − 1). It only covers a·T(n/b) + f(n); unroll the rest.
Space as the number of calls. It's the depth: Fibonacci makes exponentially many calls in O(n) space.
Check yourself
Quiz
1 / 6Multiple choice
f(n) make, as n grows?long long f(int n) {
if (n <= 1) return 1;
return f(n / 2) + f(n / 2);
}Multiple choice
g(n), which calls itself twice on n − 1?long long g(int n) {
if (n <= 1) return 1;
return g(n - 1) + g(n - 1);
}Multiple choice
Multiple choice
Multiple choice
Multiple choice
Practice
Pow(x, n) halves n each step: T(n) = T(n/2) + 1, O(log n). Merge Sort is the tie, O(n log n). Fibonacci Number shows the exponential recursion and its fix. Complexity Quiz: Medium and Hard, at the end of this section, mix recurrences with loops and library calls.