Recursion tree method: Visual walkthrough — Coding deep dive

Step 1 — What a recurrence secretly means

WHAT. A recurrence is a rule that defines the running time of a program in terms of itself. Our star example is $T (n) = a T (n / b) + f (n), T (1) = Θ (1) .$

Let's name every piece before we use it:

$T (n)$ ::: the total time to solve a problem of size $n$ (this is the thing we want to find).
$n$ ::: the size of the input — how many items, how big the list is.
$a$ ::: the branching factor — how many smaller problems this call creates. Always $a \geq 1$ .
$b$ ::: the shrink factor — each smaller problem is $1/ b$ the size. Always $b > 1$ (so problems really do get smaller).
$f (n)$ ::: the local cost — the work this call does by itself, NOT counting the recursive calls it makes (splitting, combining, one comparison — whatever the algorithm does at this level).
$T (1) = Θ (1)$ ::: the base case from the definition box — a size- $1$ problem costs a fixed constant. We write it right into the recurrence so the tree knows where to stop and what the bottom costs.

WHY. The formula is self-referential: to compute $T (n)$ you need $T (n / b)$ , which needs $T (n / b^{2})$ … forever. That circular definition is useless until we unfold it. The tree is the unfolding — and the base case tells the unfolding when to halt.

PICTURE. One call = one box. It does $f (n)$ work itself (orange), then hands off $a$ copies of a problem of size $n / b$ to children below.

Step 2 — Grow the tree one level down

WHAT. Replace each $T (n / b)$ by its own recurrence. A size- $n / b$ call does $f (n / b)$ work itself and spawns $a$ children of size $n / b^{2}$ .

$T (n) = f (n) + a [f (n / b) + a T (n / b^{2})] = f (n) + a f (n / b) + a^{2} T (n / b^{2}) .$

Annotating the growing sum:

$f (n)$ ::: the root's own work (level $0$ ).
$a f (n / b)$ ::: $a$ children, each doing $f (n / b)$ work (level $1$ ).
$a^{2} T (n / b^{2})$ ::: the leftover un-unfolded lump — $a^{2}$ grandchildren each of size $n / b^{2}$ (level $2$ , not expanded yet).

WHY. Every time we substitute, one more fully-known level ( $f$ -terms) peels off and the unknown $T$ retreats one level deeper. If we keep going until sizes reach $1$ , the remaining $T$ becomes $T (1) = Θ (1)$ (the base case) and the whole tree turns into pure known costs — no more mystery $T$ .

PICTURE. Two full levels drawn. Count the boxes per row: $1$ , then $a$ . Watch the size labels shrink: $n \to n / b \to n / b^{2}$ .

Step 3 — The width of level $i$

WHAT. How many boxes sit at depth $i$ ?

$nodes (i) = a^{i} .$

$i$ ::: the level index — a counter for which row we're on. $i = 0$ is the root, $i = 1$ its children, and so on downward. (This is the very symbol the summation later will run over.)
$a^{i}$ ::: multiply the branching by itself $i$ times. Level $0$ has $a^{0} = 1$ node; level $1$ has $a$ ; level $2$ has $a \cdot a = a^{2}$ .

WHY. Each box makes exactly $a$ children. Multiplying the count by $a$ once per level is the definition of raising $a$ to a power. That is why an exponential $a^{i}$ — not $a \cdot i$ — appears: repeated multiplication, never repeated addition.

PICTURE. The row counts light up as powers of $a$ (here $a = 2$ : $1, 2, 4, 8$ ). The tree fans out.

Step 4 — The size at level $i$ , and how deep it goes

WHAT. A box at level $i$ has size $\frac{n}{b ^{i}},$ and the tree ends when that size hits the base case $1$ .

$b^{i}$ ::: divide by $b$ once per level, $i$ times over → $n \to n / b \to n / b^{2} \to \dots \to n / b^{i}$ .
Stop when $\frac{n}{b ^{i}} = 1$ — that's exactly the base-case size from Step 1.

Solve for the stopping level: $\frac{n}{b ^{i}} = 1 \Rightarrow b^{i} = n \Rightarrow i = lo g_{b} n .$

$lo g_{b} n$ ::: "how many times must I divide $n$ by $b$ to reach $1$ ?" That is literally the definition of a logarithm — the inverse of exponentiation. We use $lo g$ here (not, say, $n / b$ ) precisely because we're repeatedly dividing, and division-by- $b$ -until-1 is what $lo g_{b}$ counts. In this whole page, " $lo g_{b} n$ " always means "the number of levels the tree has."

So the tree has $== lo g_{b} n ==$ levels, indexed $0, 1, \dots, lo g_{b} n$ .

WHY. Depth is not controlled by how many children you make ( $a$ ) — it's controlled by how fast the size shrinks ( $b$ ). Fast shrink ⇒ shallow tree; slow shrink ⇒ deep tree.

PICTURE. A vertical ruler on the left showing size collapsing $n, n / b, n / b^{2}, \dots, 1$ and the height $lo g_{b} n$ marked.

Step 5 — Work done by a whole level

WHAT. Multiply how many boxes (Step 3) by how much each costs (Step 4's size fed into $f$ ):

$W (i) = how many a^{i} \cdot cost of one f (\frac{n}{b ^{i}}) .$

$a^{i}$ ::: number of boxes on level $i$ (Step 3).
$f (n / b^{i})$ ::: the local cost each of those boxes pays, because each has size $n / b^{i}$ (Step 4).
$W (i)$ ::: the total work of that entire row.

WHY. Total effort of a row = (people in the row) × (effort each). Same as counting money: coins × value-per-coin. We add rows, not individual boxes, because rows are the natural bookkeeping unit.

PICTURE. One highlighted row; a bracket labels the row total $a^{i} f (n / b^{i})$ .

Step 6 — Add all the rows: the master formula appears

WHAT. Now — and only now, with $i$ , $lo g_{b} n$ , $Θ (\cdot)$ and the base case all defined — we write the total. It is the sum of every row's work (Step 5), from the top ( $i = 0$ ) to the leaves ( $i = lo g_{b} n$ ):

$T (n) = i = 0 \sum l o g_{b} n a^{i} f (\frac{n}{b ^{i}})$

$i = 0 \sum l o g_{b} n$ ::: " $\sum$ " means add up; the index $i$ (defined in Step 3) runs from the root row $0$ down to the last row $lo g_{b} n$ (defined in Step 4).
the summand $a^{i} f (n / b^{i})$ ::: the row total $W (i)$ from Step 5.

The very bottom row (the leaves) has $a^{l o g_{b} n}$ boxes. A useful identity rewrites that in terms of $n$ : $a^{l o g_{b} n} = n^{l o g_{b} a} .$

WHY this identity is true (change of base + exponent rules, step by step). Take logs base $b$ of both sides — a valid move because $lo g_{b}$ is a one-to-one function, so two numbers are equal exactly when their logs are.

Left side: $lo g_{b} (a^{l o g_{b} n}) = (lo g_{b} n) (lo g_{b} a)$ , using the power rule $lo g_{b} (x^{k}) = k lo g_{b} x$ (a power inside a log comes out front as a multiplier).
Right side: $lo g_{b} (n^{l o g_{b} a}) = (lo g_{b} a) (lo g_{b} n)$ , by the same rule.
Both sides equal the same product $(lo g_{b} n) (lo g_{b} a)$ — multiplication doesn't care about order — so the originals are equal. $✓$

Now the leaf cost:

Each leaf is a size- $1$ base case, so it costs $T (1) = Θ (1)$ — the fixed constant $c$ we pinned down in the opening definition box. (This is the assumption made explicit: without a stated base-case cost the leaves would have no value to sum.)
Total leaf cost $=$ (number of leaves) $\times$ (cost each) $= n^{l o g_{b} a} \cdot Θ (1) = Θ (n^{l o g_{b} a})$ .

Nothing is guessed — we gathered every box, grouped by row, summed, and folded the base case into the bottom row. This is the parent note's boxed result, now earned.

PICTURE. The full tree with a running total on the right stacking up each $W (i)$ into the grand sum, and the leaf row labelled with its $Θ (1)$ base-case cost.

Step 7 — Where does the sum concentrate? The three verdicts

WHAT. Suppose $f (n) = n^{d}$ (the common case — $d$ is just the exponent of the polynomial cost). Then a row's work is $W (i) = a^{i} (\frac{n}{b ^{i}})^{d} = n^{d} (\frac{a}{b ^{d}})^{i} .$

$n^{d}$ ::: the root's cost, pulled out front (it doesn't depend on $i$ ).
$r = \frac{a}{b ^{d}}$ ::: the ratio between one row's total and the row above it. Each step down multiplies the row work by $r$ . This is a geometric series — a sum where each term is a fixed multiple of the last (see Geometric Series).

Now the whole answer depends only on whether $r$ is below, equal to, or above $1$ :

Ratio $r = a / b^{d}$	Rows go…	Who dominates	Answer
$r < 1$ (i.e. $a < b^{d}$ )	shrink downward	the root	$Θ (n^{d})$
$r = 1$ (i.e. $a = b^{d}$ )	stay equal	every row equally	$Θ (n^{d} lo g n)$
$r > 1$ (i.e. $a > b^{d}$ )	grow downward	the leaves	$Θ (n^{l o g_{b} a})$

$r < 1$ : a decreasing geometric series sums to at most a constant times its first term $n^{d}$ → root wins.
$r = 1$ : every one of the $lo g_{b} n + 1$ rows costs $n^{d}$ → multiply → the $lo g$ factor.
$r > 1$ : an increasing geometric series is dominated by its last term (the leaves) → $n^{l o g_{b} a}$ wins.

WHY. We use a geometric series (not arithmetic) because rows are related by multiplication by $r$ , exactly matching Step 3's "multiply by $a$ each level". The direction of $r$ is the single knob that decides everything — this is the Master Theorem, derived.

PICTURE. Three little bar charts side by side — bars shrinking, level, and growing down the rows — with the dominating region shaded.

Step 8 — Edge & degenerate cases (so nothing surprises you)

WHAT. Three boundary situations the smooth formula must still handle.

(a) $a = 1$ — no branching (e.g. Binary Search, $T (n) = T (n /2) + 1$ ). Every row has $a^{i} = 1^{i} = 1$ box. The tree is a single chain, not a fan. Row work is just $f (n / b^{i})$ , and depth is still $lo g_{b} n$ . For binary search $f = 1$ , so total $= \sum 1 = Θ (lo g n)$ . No leaf explosion, because the leaf count $n^{l o g_{b} 1} = n^{0} = 1$ : a single base-case leaf costing $Θ (1)$ .

(b) Sizes shrink at different rates — unbalanced tree ( $T (n /3) + T (2 n /3) + n$ ). There is no single $b$ . Instead we bound the tree between its shortest branch (divide by $3$ : depth $lo g_{3} n$ ) and longest branch (multiply survivors by $2/3$ : depth $lo g_{3/2} n$ ).

WHY each full level still sums to $\leq n$ — the invariant, level by level. Give every node a label equal to its own size. The root's label is $n$ . When a node of size $s$ splits, its two children get labels $s /3$ and $2 s /3$ , which add back to $s$ — splitting preserves the parent's total. So the sum of all labels on any complete level equals the sum on the level above it, which by induction is always $\leq n$ . Because $f$ is linear ( $f (s) = s$ ), the work on a level equals the sum of its labels $\leq n$ . This holds at every depth, not just the top — that's the whole point of the invariant. (Deep down, short branches finish early, so real levels sum to strictly less than $n$ , still $\leq n$ .) With $Θ (lo g n)$ levels each $\leq n$ : $T (n) = Θ (n lo g n)$ .

(c) $n$ not a clean power of $b$ . Then $lo g_{b} n$ isn't a whole number and the last level is ragged. We simply round: depth is $⌈ lo g_{b} n ⌉$ . Rounding changes the level count by at most $1$ , which is absorbed by $Θ (\cdot)$ . So the answer is unchanged — the formula is robust.

WHY. A derivation you can only apply to perfectly balanced, power-of- $b$ inputs would be useless in practice. Covering $a = 1$ , unbalanced splits, and non-powers shows the method survives every real recurrence.

PICTURE. Three mini-trees: a straight chain ( $a = 1$ ), a lopsided tree with short/long paths and the size-labels adding back to the parent marked, and a ragged last row for non-power $n$ .

The one-picture summary

Everything above, compressed: the tree, its three knobs (Depth, Width, Work), the row-sum, the base-case leaves, and the three verdicts driven by the ratio $r = a / b^{d}$ .

Recall Feynman: the whole walkthrough in plain words

A boss gets a job of size $n$ and does a little work himself — that's $f (n)$ . Then he splits it into $a$ smaller jobs, each of size $n / b$ , and hands them down. Every helper does the same thing to their piece, until a job is size $1$ — the tiniest job, done directly for a fixed tiny cost (that's the base case, $Θ (1)$ ). Draw this as a family tree of jobs.

To find the total effort, don't chase individual workers — add up one row at a time. A row at depth $i$ has $a^{i}$ workers (multiply by $a$ each step down), each holding a job of size $n / b^{i}$ , so the row's effort is $a^{i} f (n / b^{i})$ .

How tall is the tree? Keep dividing $n$ by $b$ until you reach size $1$ — that takes $lo g_{b} n$ steps, so that's the height. Now stack up all the row-efforts, including the bottom row of tiny base-case jobs. Whether the tree's work piles up at the top (boss does most), spreads out evenly, or crashes down to the bottom (a riot of tiny workers) depends on one number: $r = a / b^{d}$ . Smaller than $1$ → top wins ( $n^{d}$ ). Exactly $1$ → everyone shares, giving an extra $lo g$ . Bigger than $1$ → the swarm of leaves wins ( $n^{l o g_{b} a}$ ). That single comparison is the whole Master Theorem, and you just drew it.

Connections

3.1.09 Recursion tree method (Hinglish) — the parent topic this walkthrough visualises.
Master Theorem — Step 7's three verdicts are its three cases.
Geometric Series — the sum tool that decides who dominates.
Big-O Notation — the $Θ/ O /Ω$ notation defined up top; how we bound each row and drop constants.
Divide and Conquer — the algorithm family that produces $T (n) = a T (n / b) + f (n)$ .
Merge Sort ( $a = b = 2$ ), Binary Search ( $a = 1$ ) — the $r = 1$ and $a = 1$ pictures.
Substitution Method — the guess-and-prove alternative the tree helps you set up.