Master Theorem

Let $T : \N \Rightarrow \R^+$ be a function. Suppose that:

$T(n) =$
$1$ if $n=1$
$a\cdot T(n/b) + n^d$ if $n > 1$

where $a \geq 1, b > 1$ and $d \geq 0$.

• If $d > \log_b (a)$, then $T(n) = O (n^d)$
• If $d = \log_b (a)$, then $T(n) = O (n^d \log(n))$
• If $d < \log_b (a)$, then $T(n) = O (n^{]log_b (a)})$