Recursion Tree Method

Idea

Visualize recurrence as tree where node = subproblem cost, level = total cost of that recursion depth, sum over levels gives total. Complements Master Theorem and substitution; handles forms master cannot (e.g., $n/\log n$, uneven splits).

General Form $T(n)=aT(n/b)+f(n)$

• Root cost $f(n)$
• $a$ children cost $f(n/b)$ each → level1 $a f(n/b)$
• $a^2$ nodes cost $f(n/b^2)$ → level2 $a^2 f(n/b^2)$
• Depth $\log_b n$ leaves, leaves count $a^{\log_b n}=n^{\log_b a}$ cost $Θ(1)$ each → leaf level $Θ(n^{\log_b a})$.
• Total $T(n)=\sum_{i=0}^{\log_b n-1} a^i f(n/b^i) + Θ(n^{\log_b a})$.

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

Level0 $cn^2$, Level1 $3c(n/4)^2=3cn^2/16$, Level2 $9c(n/16)^2=9cn^2/256$ → geometric ratio $3/16<1$ → sum dominated by root $Θ(n^2)$ → $T(n)=Θ(n^2)$ (Case3).

Example $T(n)=2T(n/2)+n$

Tree: root $n$, level1 $2·n/2=n$, level2 $4·n/4=n$ → each level $n$, depth $\log n$ → total $n\log n+Θ(n)=Θ(n\log n)$.

Steps

1. Draw tree, label cost per node/level.
2. Determine depth (until $n=1$ or constant).
3. Sum levels; identify geometric vs constant series.
4. Verify via substitution (induction).

Advantages

• Intuitive for guessing bound for substitution proof.
• Handles non-uniform: $T(n)=T(n/3)+T(2n/3)+O(n)$ → recursion tree shows still $O(n\log n)$ worst but more complex.

Use: Guess $T(n)$ then prove via substitution method for rigor.