Master Theorem

The master theorem allows us to easily analyze any recurrence in the form of

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

Condition	$T(n)$ Bound	Behavior
$f(n)=O\left(n^{{\log }_{b}a-ϵ}\right)$ for some $ϵ>0$	$\Theta \left(n^{{\log }_{b}a}\right)$	Recursion dominates
$f(n)=\Theta \left(n^{{\log }_{b}a}\right)$	$\Theta \left(n^{{\log }_b(a)}\log (n)\right)$	Recursion and $f(n)$ are balanced
$f(n)=\Omega \left(n^{{\log }_{b}a+ϵ}\right)$ for some $ϵ>0$ and $a\cdot f\left(\frac{n}{b}\right)\le c\cdot f(n)$ for some $c<1$ and sufficiently large $n$	$\Theta \left(f(n)\right)$	$f(n)$ dominates

Shortcut Version

If the recurrence is in the form of

$$T(n)=aT\left(\frac{n}{b}\right)+O(n^d)$$

Condition	$T(n)$ Bound
$a>b^d$	$O(n^{lo{g}_b(a)})$
$a=b^d$	$O(n^{d}log(n))$
$a<b^d$	$O(n^d)$.