Master Theorem

For master recurrence in form of

$$T(n)=aT(n/b)+f(n)$$

If there exists a constant $ϵ>0$, or $k\ge 0$:

Master Theorem

1. $f(n)=O\left(n^{{\log }_{b}a-ϵ}\right)$, then $T(n)=\Theta \left(n^{{\log }_{b}a}\right)$.
2. $f(n)=\Theta \left(n^{{\log }_{b}a{\lg }^{k}n}\right)$, then $T(n)=\Theta \left(n^{{\log }_{b}a}{\lg }^{k+1}n\right)$.
3. $f(n)=\Omega \left(n^{{\log }_{b}a+ϵ}\right)$, and $f(n)$ satisfies the regularity condition $af(n/b)\le cf(n)$ for some constant $c<1$ and all sufficiently large $n$, then $T(n)=\Theta (f(n))$.

• $f(n)$ is a driving function, $n^{{\log }_{b}a}$ is the watershed function.

Explanation

• Watershed function characterizes the number of leaves asymptotically.
• Case 1: Watershed function grows polynomially faster than driving function. Cost per level grows at least geometrically from root to leaves, the total cost of leaves dominates that of the internal nodes.
• Case 2: Driving function grows faster than watershed function by a factor of $\Theta \left({\lg }^{k}n\right)$. Each level costs roughly the same. Most of the time $k=0$.
• Case 3: Driving function grows polynomially faster. Regularity condition is satisfied most of the time. Cost of root dominates.

Proof

• Lemma 1: Cost of leaves and internal nodes.

$$T(n)=\Theta \left(n^{{\log }_{b}a}\right)+\sum _{j=0}^{\lfloor {\log }_{b}n\rfloor }{a}^{j}f\left(n/b^i\right)$$

• Lemma 2: Bound of the summation