Why guess at all?
The previous guide handed you the recursion-tree method, and you saw how unrolling T(n) = 2 T(n/2) + n into a tree all but shouts the answer Theta(n log n). But a tree drawn by hand is a sketch, not a certificate. Floors and ceilings get rounded away, the per-level sums get eyeballed, and a stray logarithmic factor is easy to lose. The substitution method — also called guess and verify — is how you turn that sketch into something airtight: you write the answer the tree suggested, then prove it by induction.
The name is honest about the order of operations. First you guess a closed form — say T(n) = O(n log n) — and only then do you verify it. The verification is an ordinary proof by induction, and it is unforgiving in exactly the right way: a wrong guess does not produce a misleading proof, it produces no proof at all. The algebra simply refuses to close. That is the whole appeal — the substitution method cannot be fooled by a plausible-looking total the way a hand-drawn tree can.
The two steps, walked through
Let us prove that T(n) = 2 T(n/2) + n is O(n log n) from start to finish. The engine is induction on the input size, and because the recurrence reaches down to size n/2 it is naturally strong induction: we are allowed to assume the bound for every size smaller than n, not just for n - 1. Here is the recurrence and the guess we will defend.
Recurrence: T(n) = 2 T(n/2) + n, T(1) = 1
Guess: T(n) <= c * n * log n (for some constant c > 0, n >= 2)
Inductive step, assume it for n/2:
T(n) <= 2 * [ c * (n/2) * log(n/2) ] + n
= c * n * (log n - 1) + n
= c * n * log n - c * n + n
= c * n * log n - (c - 1) * n
<= c * n * log n whenever c >= 1- Guess a closed form. The tree suggested Theta(n log n), so for the upper bound we try T(n) <= c n log n with c to be pinned down later.
- Assume it for smaller sizes. By strong induction suppose T(n/2) <= c (n/2) log(n/2). This is the inductive hypothesis — the only thing we are allowed to lean on.
- Substitute and simplify. Put that into the recurrence; using log(n/2) = log n - 1, the right side collapses to c n log n - (c - 1) n.
- Close the bound. The leftover term -(c - 1) n is <= 0 exactly when c >= 1, so the right side is <= c n log n — the SAME form we guessed. The induction goes through.
- Check the base case. Pick a small range (say n = 2 and n = 3) and choose c large enough that T(n) <= c n log n holds there too. Now the bound holds for all n >= 2.
Notice that the base case is not an afterthought — it is half the proof. Induction only carries a bound upward from smaller inputs, so something has to anchor the bottom. We are free to start the induction at n = 2 (rather than n = 1, where log 1 = 0 would make c n log n collapse to 0 and break) and simply pick c large enough to cover the handful of small sizes. Skipping this step is the most common silent gap in a substitution proof.
The same constant, or no proof
Here is the single subtlety that catches almost everyone the first time. To prove T(n) <= c n log n by induction, the right-hand side after substitution must close to c n log n with the very same constant c — not to c n log n plus an extra term, and not to some vague O(n log n). The constant must survive intact from the hypothesis to the conclusion. If a leftover term clings on, the induction has not closed, no matter how small that term looks.
Watch the classic wrong proof. Take T(n) = 2 T(n/2) + n and guess the wrong bound T(n) = O(n). Assume T(n/2) <= c (n/2). Then T(n) <= 2 c (n/2) + n = c n + n. A careless writer says 'that is O(n), done.' It is not done — it is c n + n, which is (c + 1) n, NOT c n. The constant grew. Push it one more level and it becomes (c + 2) n, then (c + 3) n; the constant creeps up once per level, and over log n levels it has grown to about c + log n, so T(n) is really n log n, not n. The failed induction was telling you the guess was too weak.
The strengthening trick: subtract a lower-order term
Sometimes a guess is right but the obvious form will not close, and the fix feels paradoxical: you prove a STRONGER statement to make the induction succeed. Consider T(n) = 2 T(n/2) + 1 with T(1) = 1; the recursion tree shows about n leaves each costing 1, so the answer is O(n). Yet guessing T(n) <= c n fails. Assume T(n/2) <= c (n/2); then T(n) <= 2 c (n/2) + 1 = c n + 1, and that pesky +1 means the bound c n did not reproduce itself — exactly the leftover-term failure from the last section.
The repair is to guess T(n) <= c n - d for positive constants c and d — a strictly stronger claim, since c n - d is smaller than c n. Assume T(n/2) <= c (n/2) - d. Then T(n) <= 2 (c n/2 - d) + 1 = c n - 2d + 1 = (c n - d) - (d - 1), which is <= c n - d as long as d >= 1. The bound now closes perfectly. The extra -d gave the induction a little headroom that the +1 could eat into without spilling over, and because d is a constant, c n - d is still O(n) — the strengthening costs nothing in the final answer.
It feels backwards that proving more is easier, but it is a standard move across induction proofs, not a recurrence-only quirk: a stronger hypothesis hands you a stronger tool in the inductive step. The mirror-image mistake — strengthening the wrong way, by ADDING a lower-order term, as in T(n) <= c n + d — makes the hypothesis weaker and never closes. The lesson is to subtract, not add, when an additive constant in the recurrence is leaking through.
From O to Theta, and what the method cannot promise
Everything so far proved an upper bound — a big-O result. That is only half of a tight answer. To claim T(n) = Theta(n log n) you must also prove a matching lower bound, T(n) >= c' n log n for some constant c' > 0, which is a separate substitution proof with the inequality flipped (you assume T(n/2) >= c' (n/2) log(n/2) and push down to T(n) >= c' n log n). Only when both directions close have you earned the Theta. A great many write-ups prove only the upper bound and then quietly state Theta — that is an overclaim, the most common honest-looking error in the whole topic.
Be honest, too, about what 'verified' means here. A substitution proof certifies an asymptotic bound — a statement about large n. It says nothing about the hidden constant c, which it deliberately leaves free, so it cannot tell you whether this algorithm beats another at the input sizes you actually run. Asymptotics describe scaling, not a verdict at every size; an O(n log n) method can still lose to an O(n^2) one when n is small and the dropped constants and low-order terms dominate. The substitution method answers 'how does cost grow?', not 'which is faster on my laptop today?'.
Finally, the method has a real reach but also real limits. It handles recurrences the next guide's master theorem cannot — uneven splits, added logarithms, an extra +log n in the combine — because induction does not care whether the recurrence has the tidy a T(n/b) + f(n) shape. But it is not a discovery tool, it can be fiddly when the right guess needs a clever strengthening, and a sloppy proof that lets the constant drift can 'prove' a false bound. Used with the same-constant discipline, though, it is the rigorous backbone underneath the recursion tree and the master theorem alike, and the Akra-Bazzi method of the final guide leans on the same guess-and-verify spirit.