Substitution Method

The substitution method solves a recurrence in two steps: guess the form of the answer, then prove it correct by mathematical induction. The name comes from the second step — you substitute the inductive hypothesis into the recurrence and check that the same bound survives.

That structure makes it the odd one out among the three techniques. The Master Theorem and the recursion tree both derive an answer; substitution verifies one you already have. It cannot tell you what the solution is. What it can do — and neither of the others can — is turn a plausible answer into a proof, for a recurrence of any shape whatsoever.

If a recurrence fits T(n) = aT(n/b) + f(n), the Master Theorem answers it in one line and you should use that. Substitution earns its keep when the Master Theorem cannot help:

• The subproblems are different sizes.
  • T(n) = T(n/3) + T(2n/3) + n has no single b, so the Master Theorem cannot express it.
• The input shrinks by subtraction rather than division.
  • T(n) = T(n − 1) + n is a decrease-and-conquer recurrence, outside the Master Theorem's form entirely.
• The recurrence falls in a Master Theorem gap.
  • T(n) = 2T(n/2) + n/log n sits between Cases 1 and 2, where the theorem gives no answer.
• You already suspect the answer and want to confirm it.
  • A recursion tree produces a fast guess but a loose argument; substitution turns that guess into a proof.

Since the method is induction, every proof has the same three parts. Missing any one of them means you have not proved anything:

• The inductive hypothesis — the bound you are assuming.
  • Assume the bound holds for every input smaller than n, for example T(k) ≤ ck log k for all k < n.
• The inductive step — the algebra.
  • Substitute that assumption into the recurrence and show the same bound comes out for n. This is the step the method is named after.
• The base case — where the induction starts.
  • Show the bound holds for one or more small values of n directly, choosing c large enough to make it true.

One rule governs the whole exercise: the constant must come out unchanged. If you assume T(k) ≤ ck and the algebra ends at (c + 1)n, you have not proved T(n) ≤ cn — you have proved a weaker statement with a constant that grows at every level, which over log n levels is not a constant at all.

This is the merge sort recurrence. A recursion tree suggests O(n log n), so that is the guess.

Inductive hypothesis.Assume T(k) ≤ ck log k for all k < n, for some constant c > 0 to be fixed later.

Inductive step. Substitute the hypothesis with k = n/2:

The bound closes with the same c it started with, so the step holds for any c ≥ 1.

Base case. Here the induction cannot start at n = 1: the bound cn log n equals 0 when n = 1, and T(1) = 1 is not ≤ 0. This is not a problem — asymptotic claims only need to hold for n ≥ n₀, so start at n = 2 and n = 3 instead. With T(1) = 1, the recurrence gives T(2) = 4 and T(3) = 5. Then:

Choosing c = 2 satisfies the base cases and the inductive step at once. Therefore T(n) = O(n log n).

An upper bound alone does not give Θ. The Ω proof is the same argument with every inequality reversed, and with c chosen small enough rather than large enough. Guess T(n) ≥ cn log n:

So T(n) = Ω(n log n) with c = 1. Combined with the upper bound, T(n) = Θ(n log n) — the same answer the Master Theorem gives through Case 2, now proved from first principles.

Solve T(n) = T(n − 1) + n, with T(1) = 1. The input shrinks by subtraction, so there is no b and the Master Theorem does not apply at all. A recursion tree is a single chain costing n, n−1, n−2, …, which sums to about n²/2 — so guess O(n²).

Inductive hypothesis.Assume T(k) ≤ ck² for all k < n.

Base case. T(1) = 1 ≤ c · 1² holds for c ≥ 1. Taking c = 1 satisfies everything, so T(n) = O(n²) — which matches the exact answer n(n+1)/2.

Suppose you guessed O(n) for the merge sort recurrence instead. Assume T(k) ≤ ck and substitute:

The lesson generalises: always carry an explicit constant through the algebra. Asymptotic notation inside an inductive proof conceals precisely the thing the proof is supposed to check.

Sometimes the guess is correct but the proof still fails by a single term. Take T(n) = 2T(⌊n/2⌋) + 1 and guess O(n):

The guess is right; the hypothesis is too weak. The fix is counter-intuitive: prove something stronger. Subtract a lower-order term and assume T(k) ≤ ck − d for a constant d > 0:

The stronger hypothesis carries a spare −d through the induction, and that spare term absorbs the leftover +1. Since ck − d is still O(k), proving the stronger statement proves the original one. Being handed a stronger assumption is what makes the step work — a genuinely useful trick, and one worth recognising when a proof stalls one term away from closing.

Some recurrences become familiar after a substitution of a different kind — renaming the variable. Consider T(n) = 2T(√n) + log n, which fits none of the standard patterns.

Let m = log₂n, so that n = 2^m and √n = 2^(m/2). Define S(m) = T(2^m). The recurrence becomes:

That is the merge sort recurrence, so S(m) = Θ(m log m) by Case 2 of the Master Theorem. Translating back with m = log n:

The technique is worth remembering whenever a recurrence involves √n or repeated square roots: taking a logarithm turns the square root into a halving, and halving is something every method already handles.

• Draw a recursion tree first.
  • Summing the levels loosely gives you the shape of the answer, which is exactly what substitution needs as input.
• Match it against a recurrence you already know.
  • T(n) = 2T(n/2 + 17) + n looks unfamiliar, but the +17 stops mattering for large n, so the answer is the merge sort answer: O(n log n).
• Prove loose bounds first, then squeeze.
  • If you can show O(n²) easily and Ω(n) easily, you know the truth is somewhere between, and you can narrow from both ends.
• Beware of guesses that are off by only a logarithm.
  • The difference between O(n) and O(n log n) is invisible in a sloppy tree sum but fatal in the algebra.

• Declaring victory with the wrong constant.
  • Ending at (c + 1)n and calling it O(n) is the single most common error. The constant must come out unchanged — you must reach ≤ cn, not ≤ (c+1)n.
• Forgetting the base case.
  • An inductive step without a base case proves nothing. It is also where you pin down c, since the base case is what forces c to be large enough.
• Insisting the base case must be n = 1.
  • cn log n is 0 at n = 1, so no c makes T(1) ≤ c·1·log 1 work. Asymptotic notation only cares about large n, so start the induction at n = 2 and n = 3 instead.
• Hiding the constant inside asymptotic notation mid-proof.
  • Writing "T(n) ≤ 2·O(n/2) + n = O(n)" looks fine and is wrong, because O() absorbs a constant that is silently growing at every level. Always carry an explicit c.
• Giving up when the guess is a term short.
  • Being off by a constant usually means the hypothesis needs strengthening by a lower-order term, not that the guess was wrong.
• Proving only the upper bound and claiming Θ.
  • Θ needs both directions. The Ω proof is the same argument with the inequalities reversed.

• Substitution is guess-then-prove: it verifies an answer rather than deriving one.
• Every proof needs an inductive hypothesis, an inductive step, and a base case — and the base case is where c gets pinned down.
• The constant must survive the algebra unchanged; ending at (c + 1)n is a failed proof, not a successful one.
• Never let asymptotic notation into the middle of the induction — it hides the constant you are checking.
• A proof that fails by one term usually needs a stronger hypothesis, such as ck − d instead of ck.
• It works on any recurrence, which is why it is the fallback when the Master Theorem does not apply.