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) + cn^2$. At depth $i$ there are $3^i$ nodes, each of size $n/4^i$, costing $c(n/4^i)^2 = cn^2/16^i$. The level total is $3^i \cdot cn^2/16^i = (3/16)^i\, cn^2$. Summing the geometric series with ratio $3/16 < 1$ gives at most $\frac{1}{1-3/16}cn^2 = \frac{16}{13}cn^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\tfrac{n}{2}\lg\tfrac{n}{2}\right) + \Theta(n) = cn\lg\tfrac{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\tfrac{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$.