Divide and conquer — template, correctness, recurrence: Visual walkthrough

We build everything from zero. If you have never seen a recursion tree, a logarithm, or the symbol $Θ$ , start at Step 1 anyway — each is earned before use.

Step 1 — What a recurrence actually says

WHAT. We start with one line, the promise of the divide-and-conquer template: $T (n) = how many copies a same cost rule T (smaller size \frac{n}{b}) + work here, not recursion f (n)$

Read it in plain words: the cost of a size- $n$ job equals $a$ copies of the cost of a size- $n / b$ job, plus $f (n)$ — the divide+combine work you do yourself before/after the recursive calls.

$T (n)$ = the number of basic steps a size- $n$ problem takes. $T$ is a function: feed it a size, it returns a time.
$a$ = how many subproblems each call spawns (mergesort: 2, binary search: 1, Karatsuba: 3).
$b$ = the shrink factor — inputs of size $n$ become size $n / b$ .
$f (n)$ = the work you do without recursing: splitting the array, merging the results.

WHY a recurrence at all? Because $T$ is defined in terms of itself. We cannot read off an answer; we must unfold the self-reference until it stops. That unfolding is a tree.

PICTURE. One box calling $a$ smaller boxes, each labelled with its size and its local work.

Figure — Divide and conquer — template, correctness, recurrence

Step 2 — Unfold one level: the tree grows

WHAT. Replace each $T (n / b)$ by its own definition. The recurrence applied at size $n / b$ says $T (\frac{n}{b}) = a T (\frac{n}{b ^{2}}) + f (\frac{n}{b}) .$ Substitute this into $T (n) = f (n) + a T (n / b)$ and multiply the $a$ through the bracket: $T (n) = f (n) + a [a T (\frac{n}{b ^{2}}) + f (\frac{n}{b})] = f (n) + level 1 total a f (\frac{n}{b}) + a^{2} T (\frac{n}{b ^{2}})$

Term by term on level 1:

there are $a$ children ⟶ factor $a$ ,
each does $f (n / b)$ local work (its size is $n / b$ ),
so the whole of level 1 costs $a \cdot f (n / b)$ ;
and $a \cdot a = a^{2}$ subproblems of size $n / b^{2}$ are still waiting (level 2).

WHY unfold? The self-reference $T$ is still sitting there ( $a^{2} T (n / b^{2})$ ). We keep expanding until $T$ hits a size we can answer for free (the base case). Each expansion peels off one honest, recursion-free level of work — and those we can add up.

PICTURE. Two full levels now drawn; the level-1 boxes lit up with their $a \cdot f (n / b)$ total.

Step 3 — The pattern at depth $i$

WHAT. Keep going. At depth $i$ (the root is depth $0$ ): $number of nodes = a^{i}, size of each = \frac{n}{b ^{i}}, local work each = f (\frac{n}{b ^{i}})$ So the total work on level $i$ is: $level- i cost = a^{i} f (\frac{n}{b ^{i}})$

Reading the box:

$a^{i}$ — each level multiplies the node count by $a$ again, so after $i$ levels there are $a^{i}$ nodes.
$n / b^{i}$ — each level divides the size by $b$ again, so after $i$ levels each node holds $n / b^{i}$ .
$f (\cdot)$ — plug that size into the local-work function.

WHY these two racing quantities? Node count $a^{i}$ grows up, size $n / b^{i}$ shrinks down. The entire theory of divide-and-conquer running time is a tug-of-war between these two. Whoever wins decides the answer.

PICTURE. Three levels stacked, with the $a^{i}$ / $n / b^{i}$ / $a^{i} f (n / b^{i})$ pattern annotated on a generic level $i$ .

Step 4 — Where the tree stops: counting the levels

WHAT. Recursion halts when a node's size hits $1$ (the base case). Set: $\frac{n}{b ^{i}} = 1 ⟹ b^{i} = n ⟹ i = lo g_{b} n$

$b^{i} = n$ — we divided by $b$ a total of $i$ times and reached size $1$ , so $b$ multiplied $i$ times must rebuild $n$ .
$lo g_{b} n$ — this is the definition of a logarithm: "how many times do I multiply $b$ to reach $n$ ?" That count is the height of the tree.

WHY count levels? Total cost = sum over all levels. To sum, we need to know how many levels there are — and the last (leaf) level is special, so we mark it.

PICTURE. The full tree from root to leaves, height labelled $lo g_{b} n$ , the bottom row of leaves highlighted.

Step 5 — The leaves: counting the bottom row

WHAT. The bottom level is $i = lo g_{b} n$ . Number of leaves: $a^{l o g_{b} n} = n^{l o g_{b} a}$

Each leaf is a base case costing $Θ (1)$ , so the whole leaf row costs $Θ (n^{l o g_{b} a})$ .

Why does $a^{l o g_{b} n} = n^{l o g_{b} a}$ ? This is a log identity, not a trick: $a^{l o g_{b} n} = (b^{l o g_{b} a})^{l o g_{b} n} = b^{l o g_{b} a \cdot l o g_{b} n} = (b^{l o g_{b} n})^{l o g_{b} a} = n^{l o g_{b} a}$

we rewrote $a = b^{l o g_{b} a}$ (that is just the definition of $lo g_{b} a$ ),
multiplied exponents,
regrouped to expose $b^{l o g_{b} n} = n$ .

WHY name this exponent? Call it $c_{crit} = lo g_{b} a$ . It is the cost the leaves alone contribute. It becomes our yardstick: we compare the per-level work $f$ against $n^{c_{crit}}$ to see who wins the tug-of-war.

PICTURE. Zoom on the leaf row: $a^{l o g_{b} n} = n^{l o g_{b} a}$ leaves, each a small $Θ (1)$ box.

Step 6 — Add every level: the master sum

WHAT. Total time = leaves + sum of all internal levels: $T (n) = Θ (n^{l o g_{b} a}) + i = 0 \sum l o g_{b} n - 1 a^{i} f (\frac{n}{b ^{i}})$

$Θ (n^{l o g_{b} a})$ — the leaf row (Step 5),
$\sum_{i = 0}^{l o g_{b} n - 1}$ — add up every internal level $i$ from the root ( $i = 0$ ) to just above the leaves,
$a^{i} f (n / b^{i})$ — the level- $i$ cost from Step 3.

WHY a sum, and why does it collapse? The sum's terms usually form a geometric series — each term is a fixed ratio $r$ times the previous. To make $r$ a genuine constant, we need mild conditions on $f$ :

With $r = a / b^{c}$ constant, geometric series are dominated by ONE end:

$r < 1$ (terms shrink downward) ⟶ the root dominates ⟶ $T = Θ (f (n))$ .
$r = 1$ (all terms equal) ⟶ every level costs the same, $lo g_{b} n$ of them ⟶ $T = Θ (f (n) lo g n)$ .
$r > 1$ (terms grow downward) ⟶ the leaves dominate ⟶ $T = Θ (n^{l o g_{b} a})$ .

Those three outcomes are exactly the three cases of the Master Theorem — but now you see why three cases exist: a geometric series has only three moods.

PICTURE. A bar per level (bar height = that level's cost) for the three moods: shrinking bars, flat bars, growing bars.

Step 7 — Four real algorithms, seen side by side

WHAT. Plug in landmark recurrences and read the bars. One representative per mood.

WHY these four? Flat ( $r = 1$ ), the degenerate $a = 1$ chain, root-heavy ( $r < 1$ ), and leaf-heavy ( $r > 1$ ) — the picture now covers every mood the bars can take.

PICTURE. Four mini-trees with their bar-profiles: mergesort (flat), binary search (thin chain), root-dominated (top-heavy, shrinking), Karatsuba (bottom-heavy, growing).

Step 8 — Degenerate & edge cases the picture must cover

WHAT. Never leave a scenario undrawn. Four corners:

$a = 1$ (binary search): the "tree" is a single vertical chain — no branching. Only the height $lo g_{b} n$ matters. Not a bug; the sum still works, it just has one node per level.
$b = 1$ (size never shrinks): then $n / b^{i} = n$ forever — infinite recursion. The tree has no bottom. This is the no-progress failure; the recurrence has no solution because the algorithm never terminates. (Matches the parent's base-case warning.)
$n = 1$ at the top: we are already a leaf. $T (1) = Θ (1)$ , zero recursive calls. The sum from Step 6 is empty; the boxed formula still returns $Θ (1^{l o g_{b} a}) = Θ (1)$ . ✓
Master-Theorem gap — $T (n) = 2 T (n /2) + n lo g n$ : here $f$ is not a clean power, so the ratio $r$ drifts with the level instead of staying constant — $f$ sits a log-factor above $n^{c_{crit}} = n^{1}$ . Not clean geometric ⟶ Master Theorem gives no case. The tree still works: each of the $lo g n$ levels costs $\approx n lo g n$ , summing to $Θ (n lo g^{2} n)$ . Use the tree, or Recurrence Relations / Akra–Bazzi.

WHY show these? Cases 1–3 are where a naive reader thinks the machinery "breaks"; it does not — the tree formula absorbs them. Case 4 is where the shortcut breaks but the tree survives — proof that the picture is the fundamental object, the Master Theorem merely its clean corollary.

PICTURE. Four small panels: chain ( $a = 1$ ), bottomless tree ( $b = 1$ ), single leaf ( $n = 1$ ), and the $n lo g n$ near-miss with its slightly-rising bars.

The one-picture summary

Everything on one canvas: the tree with $a^{i}$ nodes and $n / b^{i}$ sizes per level, the height $lo g_{b} n$ , the $n^{l o g_{b} a}$ leaves, the per-level bar profile, and the three verdicts (root / flat / leaves win) branching off the ratio $r = a / b^{c}$ .

Recall Feynman retelling — say it back in plain words

A big job splits into $a$ smaller jobs of size $n / b$ , and you pay $f (n)$ yourself to split and glue. Draw that as a tree. Going down one level multiplies the number of jobs by $a$ and divides each job's size by $b$ . So level $i$ has $a^{i}$ jobs of size $n / b^{i}$ , doing $a^{i} f (n / b^{i})$ total work. The tree ends when size hits $1$ , which takes $lo g_{b} n$ levels — that's just "how many halvings to reach one." The bottom row has $n^{l o g_{b} a}$ leaves, kept as a separate term because leaves do only free base-case work — which is why the $f$ -sum stops one row short, at $lo g_{b} n - 1$ . Now stack the work of every level as bars. Provided $f$ is a nice power like $n^{c}$ , each level is a fixed multiple $r = a / b^{c}$ of the one above, so the bars either shrink (root wins → $Θ (f)$ ), stay flat (all equal → $Θ (f lo g n)$ ), or grow (leaves win → $Θ (n^{l o g_{b} a})$ ). Those three bar-shapes ARE the three Master-Theorem cases. $2 T (n /2) + n^{2}$ shrinks → $n^{2}$ ; mergesort's bars are flat → $n lo g n$ ; Karatsuba's grow → $n^{1.585}$ . And when $f$ isn't a clean power (like $n lo g n$ ), $r$ drifts, the shortcut shrugs, but the tree still hands you $n lo g^{2} n$ . The tree is the truth; the theorem is just its tidy summary.

Q: In the tree, how many nodes and what size at depth

i

a^{i}

nodes, each of size

n / b^{i}

Q: Why exactly

lo g_{b} n

levels?

Size shrinks by

b

each level;

n / b^{i} = 1

gives

i = lo g_{b} n

— the number of

b

-fold shrinks to reach size

1

Q: Why does the

f

-sum run only to

lo g_{b} n - 1

The leaf row at

i = lo g_{b} n

does base-case work, counted separately as

Θ (n^{l o g_{b} a})

; including it in the

f

-sum would double-count.

Q: What makes the ratio

r = a / b^{c}

a true constant?

f

being a clean power

Θ (n^{c})

, positive and monotone; then

r

is level-independent and the geometric-series argument holds.

Q: How many leaves, and why does that exponent matter?

a^{l o g_{b} n} = n^{l o g_{b} a}

leaves;

lo g_{b} a

is the watershed exponent

c_{crit}

you compare

f

against.