Intuition The one core ideaA recurrence is a running time that describes itself in terms of smaller copies of itself; the substitution method is nothing more than guessing the closed-form answer and proving that guess by induction . Everything on this page is the vocabulary you need before that sentence makes sense — we build each symbol from a picture, in an order where each one leans on the one before it.
This page is the toolbox . The parent note swings the tools; here we forge them one at a time. If a smart 12-year-old read the parent and stumbled on a symbol, the answer lives below.
Before any symbol, one picture. When you run a program on an input, it does some number of basic steps (a comparison, an addition, a swap). More input usually means more steps.
n n how big the input is — how many numbers to sort, how many items in a list. The letter n
Picture: a row of n
T ( n ) T ( n ) number of basic steps the program takes when the input has size n T Time ; the ( n ) n
Picture: a machine with a dial reading n T ( n )
Why the topic needs it: the whole game is to find a simple formula for T ( n ) T ( n ) itself , which is the next idea.
A recurrence is an equation that defines T ( n ) T smaller inputs, plus some extra local work.
Example: T ( n ) = 2 T ( n /2 ) + n
Read it aloud: "to handle size n two sub-jobs of size n /2 n
Let us name every piece of that equation, because the parent uses the general shape T ( n ) = a T ( n / b ) + h ( n )
Definition The four pieces ofT ( n ) = a T ( n / b ) + h ( n )
a how many smaller sub-jobs you make (a whole number, a ≥ 1 b by what factor each sub-job shrinks (so a sub-job has size n / b n / b size of one sub-job (input divided by b h ( n ) extra local cost at this level (the "glue" work, like combining results).
Intuition Why "self-describing" is the whole trickA recurrence hides the answer inside itself, like a mirror facing a mirror. To reach the real total you'd have to unroll it forever. The substitution method dodges that: instead of unrolling, it guesses the total and checks the guess survives one step of the mirror. That is why we need every tool below.
Why the topic needs it: the substitution method exists only to turn a self-describing T ( n )
The recurrence 2 T ( n /2 ) + n halving . "How many times can I halve n 1
log 2 n log 2 n n how many times must you halve n 1
log 2 8 = 3 8 → 4 → 2 → 1 Picture: a staircase going down by dividing by 2 each step; the number of steps is log 2 n
Intuition Why log and not something else?Divide-and-conquer repeatedly divides the input. Repeated division is the exact opposite of repeated multiplication, and "how many multiplications/divisions" is precisely what a logarithm counts. No other tool answers "how many halvings"; that is why log
The parent uses one algebra fact about logs. Here it is, earned:
n 0 = 1 log log 2 1 = 0 zero halvings — you are already at 1). So c n log n n = 1 c ⋅ 1 ⋅ 0 = 0 T ( 1 ) n 0 = 2
Why the topic needs it: the target bound O ( n log n ) is a log; you cannot manipulate it without the halving picture and the subtraction identity.
We never prove T ( n ) bound it. Three symbols express "how fast does it grow, ignoring constants and small n
O Ω Θ Big-O Big-Omega Big-Theta )
T ( n ) = O ( g ( n )) T no faster than g c > 0 T ( n ) ≤ c g ( n ) n upper ceiling.)T ( n ) = Ω ( g ( n )) T no slower than g T ( n ) ≥ c g ( n ) lower floor.)T ( n ) = Θ ( g ( n )) T sandwiched between two copies of g tight answer.)
Intuition Why constants get ignoredA faster computer just multiplies every step count by a fixed factor — it changes c shape . O /Ω/Θ algorithm , not the laptop.
c n 0
c choose once to make T ( n ) ≤ c g ( n ) n 0 n ≥ n 0 Picture: c g ( n ) n 0 T ( n )
Common mistake The single-c same c c c + 1 log n Θ ( n log n ) O ( n )
Why the topic needs it: the substitution method's entire output is "T ( n ) ≤ c g ( n ) O c n 0
The substitution method is induction wearing a costume (see Mathematical Induction ).
Intuition Why a recurrenceloves induction
A recurrence already relates T ( n ) T smaller inputs — and "assume it for smaller inputs" is exactly what the inductive step lets you do. The shapes match perfectly, so we don't solve the recurrence; we verify a guess by dropping it into the IH.
Definition Inductive hypothesis (IH) hereThe IH is the guess itself, applied to smaller inputs: "T ( k ) ≤ c f ( k ) k < n k = n / b n / b < n
Why the topic needs it: "prove by induction" is literally step 2 of the method. The base case, the IH, and the single-c
Definition Absorb the residualAfter substituting you get c f ( n ) + ( leftover ) residual is that leftover. You absorb it by showing the leftover is ≤ 0 ≤ c f ( n )
Picture: a set of scales already tipped in your favour; a negative leftover pushes it further down, never up.
Why the topic needs it: these are the middle two letters of the parent's mnemonic G-A-S-A-B (Guess, Assume, Substitute , Absorb , Base). They are the actual moves of the proof.
Recurrence T of n = a T of n over b + h of n
Logarithm log n = halving count
Target bound O of n log n
Big-O Big-Omega Big-Theta with constant c and n0
Mathematical Induction base plus step
Inductive hypothesis for smaller n
Cover the right side and answer aloud; then reveal.
What does T ( n ) The number of basic steps the program takes on an input of size n
What is a recurrence? An equation that defines T ( n ) T
In T ( n ) = a T ( n / b ) + h ( n ) a b h ( n ) a b n / b h ( n )
What real question does log 2 n How many times you must halve n 1
State the identity used to split log ( n /2 ) log 2 ( n /2 ) = log 2 n − 1 log 2 2 = 1
Why can't the base case start at n 0 = 1 n log n log 2 1 = 0 c n log n = 0 n = 1 T ( 1 )
What do O Ω Θ Upper bound, lower bound, and both-at-once (tight) bound on growth, ignoring constants.
What are c n 0 c n 0
State the two parts of a proof by induction. Base case (prove P ( n 0 ) P ( n )
What is the inductive hypothesis in this method? The guess T ( k ) ≤ c f ( k ) k < n k = n / b
Why is substituting the IH's bound legal for an upper bound? Replacing T ( n / b ) ≥ ≤
What does "absorb the residual" require? The leftover term must be ≤ 0 c
