Master Theorem

The master theorem provides a general boilerplate solution for solving recurrence relations (like divide and conquer algorithms) that satisfy a particular format.

Definition

Let $f$ be an increasing function satisfying a recurrence relation:

$f(n)=af\left({\frac {n}{b}}\right)+cn^{d}$

Whenever

• $n=b^{k}$ for some $k\geq 1$, $a\geq 1$
• $b$ is an integer > 1
• $c$ and $d$ are real numbers ≥ 0

Then

$f(n)=af\left({\frac {n}{b}}\right)+cn^{d}={\begin{cases}\Theta \left(n^{d}\right)&a<b^{d}\\\Theta \left(n^{d}\log {n}\right)&a=b^{d}\\\Theta \left(n^{\log _{b}{a}}\right)&a>b^{d}\end{cases}}$

Proof

Proposition. If $a=b^{d}$ and $n$ is a power of $b$, then a function $f$ satisfying the recurrence relation $f(n)=af(n/b)+cn^{d}$ is of the form $f(n)=f(1)n^{d}+cn^{d}\log _{b}{n}$

Proof. Let $k=\log _{b}{n}$. Then

${\begin{aligned}f(n)&=cn^{d}+ac\left({\frac {n}{b}}\right)^{d}+a^{2}c\left({\frac {n}{b^{2}}}\right)^{d}+\dots +a^{k-1}c\left({\frac {n}{b^{k-1}}}\right)^{d}+a^{k}f(1)\\&=a^{k}f(1)+\sum _{j=0}^{k-1}a^{j}c\left({\frac {n}{b^{j}}}\right)^{d}\\&=a^{k}f(1)+\sum _{j=0}^{k-1}cn^{d}\\&=a^{k}f(1)+kcn^{d}\\&=a^{\log _{b}{n}}f(1)+c(\log _{b}{n})n^{d}\\&=b^{d\log _{b}{n}}f(1)+c(\log _{b}{n})n^{d}\\&=n^{d}f(1)+c(\log _{b}{n})n^{d}\\&=O(n^{d}\log {n})\end{aligned}}$