= Solution
The standard three-case <master theorem> concerns
$$
T(n)=aT(n/b)+f(n),\qquad a\geq1,\quad b>1,
$$
with constant base-case cost and eventually nonnegative $f$. Put $d=\log_b a$.
* If $f(n)=O(n^{d-\epsilon})$ for some $\epsilon>0$, then $T(n)=\Theta(n^d)$.
* If $f(n)=\Theta(n^d)$, then $T(n)=\Theta(n^d\log n)$.
* If $f(n)=\Omega(n^{d+\epsilon})$ for some $\epsilon>0$ and $a f(n/b)\leq c f(n)$ eventually for a constant $c<1$, then $T(n)=\Theta(f(n))$.
In a <divide-and-conquer algorithm>, $a$ counts recursive subproblems, $n/b$ is their size, and $f$ accounts for splitting and combining. The comparison with $n^{\log_b a}$ identifies whether leaves, all levels, or the upper levels dominate the <running time>. The polynomial gap and the third case's regularity condition are part of this version of the theorem.
Back to article page
