Master theorem

The master theorem (or master method) is a “cookbook” method for finding the asymptotic bounds of recurrences of the form:

$$T(n)=aT\left(\frac{n}{b}\right)+f(n)$$

where $a>0$ and $b>1$ are constants, and $f(n)$ is a driving function. A recurrence that looks like this is called a master recurrence.

There are three conditions associated with the master theorem.

1. If $f(n)\in O(n^{{\log }_{b}a-ϵ})$ for some positive constant $ϵ$, then $T(n)\in \Theta (n^{{\log }_{b}a})$.
2. If $f(n)\in \Theta (n^{{\log }_{b}a})$, then $T(n)\in \Theta (n^{{\log }_{b}a}\log n)$.
3. If $f(n)\in \Omega (n^{{\log }_{b}a+ϵ})$ for some positive constant $ϵ$, and $af(n/b)\le cf(n)$ for $c\in (0,1)$, then $T(n)\in \Theta (f(n))$.

Each term in the theorem is intentional. We don’t need a tight big-Θ bound for cases 1 and 3, and in these cases a possible solution may not involve only minor algebraic manipulations.

Any time all three conditions aren’t satisfied, we must turn to more complicated hand-proofs, like the substitution method.