Noesis
3.1.8 · D5Complexity Analysis

Question bank — Substitution method for recurrences

1,964 words9 min read↑ Back to topic

The parent note built the engine G-A-S-A-B (Guess → Assume → Substitute → Absorb → Base). Everything below stress-tests whether you understand it, not whether you can grind algebra.

The figure below fixes these names to a picture before you meet them in the traps — look at it once, then the wikilinked Recursion Tree Method and Master Theorem boxes on this page will mean something concrete.

Figure — Substitution method for recurrences

True or false — justify

Every statement is a claim someone actually believes. Decide, then read the reasoning.

If I prove , I have proved .
False. Induction must reproduce the same constant it assumed. A constant that grows by each level accumulates over levels, so the true bound is , not .
-notation hides constants anyway, so it's fine if the constant grows a little during the inductive step.
False. Big- hides one fixed constant across all ; it does not permit a constant that changes with the recursion depth. A per-level increment is a hidden factor, not a hidden constant.
A recurrence and an induction proof have the same "shape".
True. A recurrence relates to smaller inputs, and induction proves a claim at from claims at smaller inputs. That structural match is why substitution works — see Mathematical Induction.
If the guess fails, the recurrence has no closed-form solution.
False. A failed guess only means that guess is wrong (usually too tight). The recurrence still has a solution; you simply try a looser bound like .
Choosing a stronger inductive hypothesis (e.g. ) makes the proof harder because you're claiming more.
False. A stronger hypothesis gives you more to assume about smaller inputs, which supplies the extra slack () needed to absorb stubborn residuals. Claiming more, paradoxically, makes the step easier.
The substitution method solves the recurrence algebraically.
False. It never derives the answer from scratch; it verifies a candidate you already guessed. The guess usually comes from a recursion tree or the Master Theorem.
You can always start the base case at .
False. For an bound, makes at , which cannot bound a positive . You must pick where , e.g. .
For an upper bound, replacing by is a legal move.
True. We assumed , and substituting a larger (or equal) quantity onto the right side of a only preserves the inequality direction.
The residual left after massaging must equal exactly zero.
False. It must be , not exactly . Any non-positive leftover can only help the "", so with is perfectly fine.
Proving a lower bound () uses the same steps as the upper bound.
True in structure, flipped in direction. You assume and need the residual to be ; every inequality reverses, but G-A-S-A-B is identical.
When is not a power of , the recurrence literally makes no sense as written.
True in the raw form, but harmless. Real recurrences use or (floor/ceiling) so sizes stay whole numbers; substitution still works because those differ from by less than and get swallowed into the constant.

Spot the error

Each block contains a flaw. Name it.

", and is linear, so . ✓"
The error is treating a growing constant as harmless. The step produced , so the inductive invariant was not reproduced; the proof is invalid and the real answer is .
", done."
The error is hiding the additive cost inside . That very may be the term that cannot be absorbed; you must carry its explicit constant until the final line.
"We proved the inductive step, so the theorem holds — no need to check small ."
The error is omitting the base case. Without grounding, induction can 'prove' false statements; the base case also fixes large enough for the smallest inputs.
"Guess . Assume . Substitute: . Since is still for large , we're done."
The error is a false inequality: requires , impossible for positive . The residual is never , so the guess fails.
". I'll guess ; substituting gives , easily absorbed — so ."
No error in the math — the absorption is valid, so is a correct (but loose) bound. The 'error' is believing it's the tight answer; the true bound is .
"To prove , I show and note the residual is , which helps."
The error is the direction: for a lower bound the residual must be , not . A non-positive residual would break a inequality.
"Because might be fractional, I'll just round it to and ignore floors — no harm done, right?"
Usually harmless but you must say why: the floor/ceiling changes each subproblem size by , and that difference vanishes into the constant for large . Silently dropping it without that justification is the error.

Why questions

Answer with the mechanism, not a slogan.

Why does an unabsorbable residual translate into an extra factor?
Each of the recursion levels contributes one un-cancelled ; summing across all levels gives — see the Recursion Tree Method for the level-by-level picture.
Why does the substitution method need a guess at all, unlike the Master Theorem?
Substitution only verifies; it has no machinery to generate the answer. The Master Theorem or a recursion tree supplies the candidate, then substitution proves it rigorously.
Why is subtracting a lower-order term the right strengthening, rather than adding one?
Adding () would demand you prove more on the left but give slack on the wrong side. Subtracting () tightens the assumed bound, leaving spare negative room to swallow the residual.
Why must the constant be fixed before the induction, not chosen fresh each step?
A fresh per step is a hidden function of the depth; the invariant "" would then mean different things at different , so the chain of implications collapses.
Why does replacing with its upper bound increase the right side yet keep the proof valid?
For an upper-bound proof we want the right side as large as (or larger than) the truth; a larger right side that still stays proves the smaller true value does too.
Why is a looser guess sometimes easier to prove than a tight one?
A looser target leaves a bigger gap for the residual to fit into, so the "" absorption condition is easier to satisfy. Tightness costs slack.
Why can we ignore floors and ceilings (, ) when doing substitution?
They perturb each subproblem size by less than , a lower-order effect that the constant (chosen large enough) absorbs; the asymptotic bound is unchanged for .

Edge cases

Boundary and degenerate scenarios the method must survive.

What happens to the guess exactly at ?
It collapses to because , so it cannot bound a positive . This is precisely why the base case starts at .
If in (only one subproblem), does substitution still apply?
Yes — the recipe is unchanged; you assume and absorb (the extra combine work). With the recursion is a single chain, but induction on smaller inputs still works.
For , why does the naive actually succeed where failed?
The subproblem sizes shrink the combined coefficient to , leaving residual once . The total recursive work is genuinely below linear-times-log, so linear holds.
What does it mean when the residual is exactly for all (never helps, never hurts)?
The inequality holds with equality slack, so the guess is valid but sits right at the boundary; any additive lower-order cost you overlooked could tip it, so double-check the massage.
Does the substitution method distinguish from on its own?
No — a single substitution proves one direction. For [[Big-O Big-Omega Big-Theta|]] you run it twice: once for the upper bound and once for the lower bound.
For the canonical merge sort recurrence , why is provable but not?
The massage yields residual (absorbable), while yields that no fixed can cancel — the extra work per level survives across levels.
When and , what are the two subproblem sizes and why doesn't the mismatch break the proof?
and — one bigger, one smaller than . Both are , so the inductive hypothesis still applies to each, and the half-unit gap is absorbed by the constant.
Recall Meta-check: did you reason or guess?

For each item above, ask: did I get the verdict right AND the mechanism right? A correct verdict with wrong reasoning means you pattern-matched, not understood. Re-derive that one via G-A-S-A-B.

Connections