= Solution
A <divide-and-conquer algorithm> handles a small input directly; otherwise it divides the input into smaller instances, recursively solves them, and combines their answers. With $a$ equally sized subproblems of size approximately $n/b$ and nonrecursive work $f(n)$, its <recurrence relation> has the form $T(n)=aT(n/b)+f(n)$, with constant-size base cases, $a\ge1$ and $b>1$.
Write $p=\log_b a$. The basic <master theorem> gives the following cases, with a fixed $\varepsilon>0$:
* If $f(n)=O(n^{p-\varepsilon})$, then \b[$T(n)=\Theta(n^p)$].
* If $f(n)=\Theta(n^p)$, then \b[$T(n)=\Theta(n^p\log n)$].
* If $f(n)=\Omega(n^{p+\varepsilon})$ and the regularity condition $af(n/b)\le cf(n)$ holds eventually for some $c<1$, then \b[$T(n)=\Theta(f(n))$].
For the common extended middle case, $f(n)=\Theta(n^p\log^k n)$ with fixed $k\ge0$ gives $T(n)=\Theta(n^p\log^{k+1}n)$. A <recursion tree> explains the three cases: work is dominated by its leaves, spread across comparable levels, or dominated by its top levels. The regularity condition in the last case is part of the theorem, not an optional simplification.
Back to article page
