Master Theorem

Compare $f(n)$ with $n^{\log_b a}$: if $f$ is smaller → $\Theta(n^{\log_b a})$; equal → $\Theta(n^{\log_b a}\log n)$; larger (with regularity) → $\Theta(f(n))$. Merge sort: $a=b=2$, $f=n$ → $\Theta(n\log n)$.