Recursion tree method

What is a recursion tree?

The three questions you must answer for any tree:

HOW DEEP is it? (number of levels) — controlled by how fast $n$ shrinks.
HOW WIDE is each level? (number of nodes at depth $i$ ) — controlled by branching $a$ .
HOW MUCH work per level? (sum of node values at depth $i$ ).

Then $T(n) = \sum_{\text{levels } i} (\text{work at level } i)$ .

Deriving the level counts from scratch

Take the canonical divide-and-conquer recurrence: $T(n) = a\,T(n/b) + f(n), \quad a\ge 1,\; b>1.$

Worked Example 1 — Merge Sort: $T(n) = 2T(n/2) + n$

Here $a=2,\ b=2,\ f(n)=n$ .

Step	What we do	Why this step?
Depth	$\log_2 n$ levels	Size halves each level: $n/2^i = 1 \Rightarrow i=\log_2 n$ .
Nodes at level $i$	$2^i$	Branching factor $a=2$ .
Node size at level $i$	$n/2^i$	Size shrinks by $b=2$ .
Work per level	$2^i \cdot \frac{n}{2^i} = n$	The $2^i$ cancels — every level costs $n$ .
Total	$n \times (\log_2 n + 1) = \Theta(n\log n)$	Equal work per level × number of levels.

Worked Example 2 — $T(n) = 3T(n/4) + n^2$

Here $a=3,\ b=4,\ f(n)=n^2$ .

Step	Result	Why this step?
Work at level $i$	$3^i\left(\frac{n}{4^i}\right)^2 = n^2\left(\frac{3}{16}\right)^i$	Plug into $a^i f(n/b^i)$ ; group powers of $i$ .
Ratio	$\frac{3}{16} < 1$	Geometric series with ratio $<1$ → decreasing.
Sum	$n^2\sum_i (3/16)^i \le n^2 \cdot \frac{1}{1-3/16} = \Theta(n^2)$	Convergent geometric series → constant factor.
Total	$\Theta(n^2)$	Root dominates — top level work wins.

Worked Example 3 — Unbalanced tree: $T(n) = T(n/3) + T(2n/3) + n$

Subproblems shrink at different rates, so we can't use $b$ directly. We bound the height.

Step	Result	Why this step?
Work per level	$\le n$ (sizes at a level sum to $\le n$ )	$n/3 + 2n/3 = n$ ; cost $f$ is linear, so each level sums to about $n$ .
Shortest path	$\log_3 n$ (divide by 3)	The $1/3$ branch shrinks fastest.
Longest path	$\log_{3/2} n$ (multiply by $2/3$ )	The $2/3$ branch shrinks slowest → deepest.
Total	between $n\log_3 n$ and $n\log_{3/2} n$ → $\Theta(n\log n)$	Levels $\times$ per-level work $n$ , all logs differ by constants.

Common mistake Steel-manning the classic blunders

Mistake A: "Each level costs $f(n)$ , so total = $f(n)\cdot \log n$ ." Why it feels right: In merge sort every level genuinely costs $n$ , so people overgeneralize. Fix: Level cost is $a^i f(n/b^i)$ , not $f(n)$ . It only stays constant when the $a^i$ exactly cancels the shrink in $f$ . Always compute the per-level sum.

Mistake B: "Number of leaves is $n$ ." Why it feels right: For merge sort the leaves are indeed $n$ (since $n^{\log_2 2}=n$ ). Fix: Leaves $= a^{\log_b n} = n^{\log_b a}$ . For $a=3,b=2$ that's $n^{1.58}$ , not $n$ .

Mistake C: Forgetting the geometric ratio direction. Why it feels right: People sum " $\log n$ levels of something" without checking growth. Fix: Compute ratio $r = a/b^{d}$ (where $f=n^d$ ). $r<1$ →root, $r=1$ → $\log$ factor, $r>1$ →leaves.

The 80/20 takeaway

Recall Feynman: explain to a 12-year-old

Imagine a boss with a big job. He splits it into smaller jobs and hands them to helpers. Each helper splits their job again, and so on, until jobs are tiny. Draw this as a family tree of jobs. To find how much total effort the whole company spends, write the effort next to each person and add up everyone — row by row is easiest. Sometimes the boss does the most work (top of the tree), sometimes the tiny workers at the bottom do (because there are SO many of them), and sometimes everyone does an equal share. The recursion tree just helps you see who's doing the heavy lifting.

Flashcards

What three quantities must you find for any recursion tree?

Depth (

\log_b n

), nodes per level (

a^i

), and work per level (

a^i f(n/b^i)

Total-work formula from a recursion tree for

T(n)=aT(n/b)+f(n)

T(n)=\sum_{i=0}^{\log_b n} a^i\, f(n/b^i)

How many leaves does the tree have?

a^{\log_b n} = n^{\log_b a}

, each costing

\Theta(1)

Per-level work for merge sort

2T(n/2)+n

, and why constant?

2^i \cdot (n/2^i)=n

; the branching

2^i

cancels the shrink, so every level costs

n

→ total

\Theta(n\log n)

For

T(n)=3T(n/4)+n^2

, what is the level-

i

work and the answer?

n^2(3/16)^i

; ratio

<1

→ root dominates →

\Theta(n^2)

When does the root dominate vs the leaves?

Root dominates when per-level work is a decreasing geometric series (

a<b^d

); leaves dominate when it's increasing (

a>b^d

Why does an unbalanced tree like

T(n/3)+T(2n/3)+n

give

\Theta(n\log n)

Each level sums to

\le n

and height is between

\log_3 n

and

\log_{3/2} n

, all

\Theta(\log n)

Common wrong leaf count and the fix?

Saying "

n

leaves"; correct is

n^{\log_b a}

(only equals

n

when

a=b

Connections

Master Theorem — the recursion tree is its proof/intuition engine.
Big-O Notation — level sums are bounded using asymptotic notation.
Divide and Conquer — every D&C algorithm produces a recursion tree.
Geometric Series — deciding root vs leaves is a geometric-series convergence test.
Merge Sort and Binary Search — canonical balanced/decreasing trees.
Substitution Method — alternative recurrence-solving technique (guess + induction).

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Recursion tree ka matlab simple hai: jab tum koi recursive function likhte ho, toh wo apne ko baar-baar chhote problems mein todta jaata hai. Har call ko ek node maan lo, aur uss node ke andar likh do "is call ne kitna non-recursive kaam kiya" — yaani $f(n)$ . Phir poore tree ke saare nodes ka kaam jod do, bas wahi tumhara total time $T(n)$ hai. Itna hi concept hai.

Teen cheezein dhyaan rakhni hain: tree kitna deep hai (kitne levels — yeh $\log_b n$ hota hai kyunki har level pe size $b$ se divide hoti hai), har level pe kitne nodes hain ( $a^i$ , kyunki har node $a$ bachche banata hai), aur har level ka total kaam ( $a^i \cdot f(n/b^i)$ ). Merge sort mein magic yeh hai ki har level ka kaam exactly $n$ aata hai (kyunki $2^i$ aur $n/2^i$ cancel ho jaate hain), aur $\log n$ levels hain, isliye answer $n\log n$ .

Sabse important trick: per-level kaam ko dekho — agar wo neeche jaate hue ghat raha hai (geometric series ratio $<1$ ), toh root jeet jaata hai, answer $f(n)$ . Agar barabar hai toh ek extra $\log$ factor lag jaata hai. Agar badh raha hai, toh leaves jeet jaate hain, answer $n^{\log_b a}$ . Yeh exactly Master Theorem hai, par ratta maarne ki zaroorat nahi — har baar level sum se nikaal sakte ho.

Galti se bacho: log sochte hain "har level $f(n)$ ka kaam karta hai" — galat! Sirf merge sort jaise balanced case mein aisa hota hai. Aur leaves ki ginti $n$ nahi, $n^{\log_b a}$ hoti hai. Yeh do baatein yaad rakh lo toh 80% problems clear.

What is a recursion tree?

Deriving the level counts from scratch

Worked Example 1 — Merge Sort: $T(n) = 2T(n/2) + n$

Worked Example 2 — $T(n) = 3T(n/4) + n^2$

Worked Example 3 — Unbalanced tree: $T(n) = T(n/3) + T(2n/3) + n$

The 80/20 takeaway

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Complexity Analysis

Connections