Solving recurrences

The substitution method for recurrences, explained with examples

Watch it first: the substitution method, animatedPlay the animation
By Prof. Bolts10 minute readUpdated October 2026

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.

Video lesson
Paste the YouTube embed code for this topic here.

The four steps

  1. Guess the form of the answer. Use the iteration method, a recursion tree, or experience. For 2T(n/2) + n a good guess is T(n) ≤ c·n log n.
  2. Assume it for smaller inputs. This is the inductive hypothesis, for example T(n/2) ≤ c(n/2) log(n/2).
  3. 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.
  4. 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).

Assume: T(n/2) ≤ c(n/2)·log(n/2) Substitute: T(n) ≤ 2·c(n/2)·log(n/2) + n = cn·(log n − 1) + n = cn log n − cn + n ≤ cn log n whenever c ≥ 1

The step log(n/2) = log n − 1 is where the proof works: it produces a −cn term that cancels the extra +n.

Watch the base case

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.

Try it yourself

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 studio

Example 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².

Assume: T(n − 1) ≤ c(n − 1)² Substitute: T(n) ≤ c(n − 1)² + n = cn² − 2cn + c + n ≤ cn² when −2cn + c + n ≤ 0

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:

Assume T(n/2) ≤ c(n/2) Then T(n) ≤ 2·c(n/2) + n = cn + n = (c + 1)n = O(n) ✗

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).
Guess: T(n) ≤ c·log n Assume: T(n/2) ≤ c·log(n/2) = c log n − c Then: T(n) ≤ c log n − c + 1 ≤ c log n when c ≥ 1 Base: n = 1 fails (c·log 1 = 0 < 1), so use n₀ = 2: T(2) = 2 ≤ c·log 2 = c → c = 2

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).
Assume: T(n − 1) ≤ c(n − 1) Then: T(n) ≤ cn − c + 1 ≤ cn when c ≥ 1 Base: T(1) = 1 ≤ c·1 → c = 1, n₀ = 1
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:

Guess: T(n) ≤ cn − d Assume: T(n/2) ≤ c(n/2) − d Then: T(n) ≤ 2(cn/2 − d) + 1 = cn − 2d + 1 ≤ cn − d when d ≥ 1 Base: T(1) = 1 ≤ c − d → c = 2, d = 1

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.