The substitution method for recurrences, explained with examples
The substitution method proves that a recurrence such as T(n) = 2T(n/2) + n has a particular bound, for example O(n log n). It is a proof by induction: you guess the answer, assume it holds for smaller inputs, and show it then holds for n as well. This guide walks through the method step by step, works two full examples, and shows the mistake that costs students the most marks.
Paste the YouTube embed code for this topic here.
The four steps
- Guess the form of the answer. Use the iteration method, a recursion tree, or experience. For
2T(n/2) + na good guess isT(n) ≤ c·n log n. - Assume it for smaller inputs. This is the inductive hypothesis, for example
T(n/2) ≤ c(n/2) log(n/2). - Substitute and simplify. Put the assumption into the recurrence and show that the result is at most
c·n log n, with the same c. - Check the base case. Choose c and n₀ so the first value also fits the bound.
Example 1: prove T(n) = 2T(n/2) + n is O(n log n)
Take T(1) = 1 and n a power of 2. We guess T(n) ≤ c·n log n (log base 2).
The step log(n/2) = log n − 1 is where the proof works: it produces a −cn term that cancels the extra +n.
At n = 1 the bound is c·1·log 1 = 0, but T(1) = 1. The bound fails at n = 1, and that is allowed: Big-O only needs it from some n₀ onwards. Start at n₀ = 2 instead. T(2) = 2·T(1) + 2 = 4, and we need 4 ≤ c·2·log 2 = 2c, so c = 2 works.
So T(n) ≤ 2n log n for all n ≥ 2, which means T(n) = O(n log n). The exact solution is n log₂ n + n, which sits comfortably under the bound.
Open this proof in the Recursion Studio. It plots the real values of T(n) as dots under the curve 2n log n and shades where the bound holds. Change c to 1 and watch the base case fail.
Open the studioExample 2: prove T(n) = T(n − 1) + n is O(n²)
Take T(1) = 1. Each step adds about n, so we guess T(n) ≤ c·n².
With c = 1 the condition becomes −n + 1 ≤ 0, which is true for every n ≥ 1. The base case T(1) = 1 ≤ 1·1² also holds, so c = 1, n₀ = 1 and T(n) = O(n²). The exact answer is n(n + 1)/2.
The classic mistake
Here is a wrong "proof" that T(n) = 2T(n/2) + n is O(n). It appears in exams because it looks convincing:
The error: the inductive step must prove the exact same bound, T(n) ≤ cn, with the same constant c. Showing (c + 1)n is not enough, because the constant grows by 1 at every level of the recursion and is not a constant at all. Whenever your substitution leaves an extra positive term, the guess is wrong or needs strengthening.
Practice questions
1. Prove that T(n) = T(n/2) + 1, with T(1) = 1, is O(log n).
So T(n) ≤ 2 log n for n ≥ 2, and T(n) = O(log n).
2. Prove that T(n) = T(n − 1) + 1, with T(1) = 1, is O(n).
3. Prove that T(n) = 2T(n/2) + 1, with T(1) = 1, is O(n). (Hint: the plain guess cn fails.)
The plain guess leaves an extra term: 2·c(n/2) + 1 = cn + 1, which is not ≤ cn. Strengthen the guess by subtracting a lower-order term:
So T(n) ≤ 2n − 1, and T(n) = O(n). The exact solution is 2n − 1.
Where next
To find a good guess in the first place, use the iteration method, which unrolls the recurrence level by level. If you are still unsure how a recurrence comes from code, start with writing the recurrence for merge sort.