Justification

The basic justification is very simple.

$n^{\log_b(a)}$ is the number of leaves on the tree.

• If f(n) polynomially less than $n^{\log_b(a)}$, then the number of leaves dominates in the recurrence: $\Theta(n^{\log_b(a)})$ (Rule 1).
• If f(n) polynomially more than than $n^{\log_b(a)}$, then the first appearance of f(n) in the tree dominates in the recurrence: $\Theta(f(n))$ (Rule 3). (There is a ``regularity'' condition on f(n) for this to be true that holds for nearly all functions that we'll see, so you can ignore it).
• If f(n) and $n^{\log_b(a)}$ balance, then f(n) makes a contribution at every level: $\Theta(f(n) \log n)$ (Rule 2).