Solving recurrences I: recursion-tree & substitution

Two general methods

A recurrence describes $T(n)$ in terms of $T$ on smaller arguments. Before the master-theorem shortcut, two methods solve recurrences the master theorem can't reach (unequal splits, gap cases): the recursion-tree method (to guess the answer) and the substitution method (to prove it).

Recursion trees: sum the cost per level

Draw a node per subproblem, labelled with its non-recursive (divide+combine) cost. Sum within each level, then across levels. The shape of those per-level sums tells you which term wins:

• per-level cost grows toward the leaves ⟶ the leaves dominate;
• per-level cost is constant ⟶ each level contributes equally, and the number of levels matters;
• per-level cost shrinks toward the leaves ⟶ the root dominates.

Worked tree — $T(n)=3T(n/4)+c{n}^2$. At depth $i$ there are $3^i$ nodes, each of size $n/4^i$, costing $c(n/4^i{)}^2=c{n}^2/16^i$. The level total is $3^i\cdot c{n}^2/16^i=(3/16{)}^{i}c{n}^2$. Summing the geometric series with ratio $3/16<1$ gives at most $\frac{1}{1-3/16}c{n}^2=\frac{16}{13}c{n}^2=O(n^2)$. The root alone already costs $\Theta (n^2)$, so $T(n)=\Theta (n^2)$ — the root dominates.

Worked tree — unbalanced $T(n)=T(n/3)+T(2n/3)+\Theta (n)$. Branches shrink at different rates, but every level still sums to at most $cn$ of work, and the longest root-to-leaf path is ${\log }_{3/2}n=\Theta (\lg n)$ levels. So total cost $\le cn\cdot \Theta (\lg n)=O(n\lg n)$, and it is $\Theta (n\lg n)$. (The master theorem can't touch this one — the two subproblems have different sizes.)

Substitution: guess, then prove by induction

Two steps: (1) guess the form of the bound with a symbolic constant; (2) prove it by induction, solving for the constant.

Worked proof — $T(n)=2T(\lfloor n/2\rfloor )+\Theta (n)=O(n\lg n)$. Guess $T(n)\le cn\lg n$. Inductive hypothesis: $T(\lfloor n/2\rfloor )\le c\lfloor n/2\rfloor \lg (\lfloor n/2\rfloor )$. Then

$$T(n)\le 2\left(c\frac{n}{2}\lg \frac{n}{2}\right)+\Theta (n)=cn\lg \frac{n}{2}+\Theta (n)=cn\lg n-cn+\Theta (n)\le cn\lg n,$$

where the last step holds once $c$ is large enough that the $-cn$ term swallows the $\Theta (n)$ term. The key algebra is $\lg (n/2)=\lg n-1$, which produces the crucial $-cn$.

The subtract-a-lower-order-term trick

Sometimes the naive guess almost works but leaves a stubborn additive term. For $T(n)=2T(n/2)+\Theta (1)=O(n)$, guessing $T(n)\le cn$ yields $cn+\Theta (1)$ — which is not $\le cn$. Strengthen the guess to $T(n)\le cn-d$:

$$T(n)\le 2\left(c\frac{n}{2}-d\right)+\Theta (1)=cn-2d+\Theta (1)\le cn-d,$$

as long as $d$ dominates the $\Theta (1)$. Counterintuitively, a stronger (smaller) hypothesis is easier to push through, because each recursive call contributes its own $-d$.