Definition
The Master’s Theorem is a tool for analyzing the time complexity of divide-and-conquer algorithms.
Formal Theorem
Let $a \ge 1$ and $b > 1$ be constants, $f(n)$ be a non-negative function, and $T(n)$ be defined on the non-negative integers by the recurrence $T(n) = aT(n/b) + f(n)$ with sufficient base cases, where $n/b$ means either $\lceil n/b \rceil$ or $\lfloor n/b \rfloor$.
| Form | Complexity |
|---|---|
| $f(n)=O(n^{(log_b a - \epsilon)})$ for some constant $\epsilon>0$ | $T(n)=\Theta(n^{log_b a})$ |
| $f(n)=\Theta(n^{log_b a} log^k n)$ for some constant $k\ge0$ | $T(n)=\Theta(n^{log_b a} log^{k+1}n)$ |
| $f(n)=\Omega(n^{(log_b a + \epsilon)})$ for some constant $\epsilon>0$ and $\exists c < 1, N > 0$ such that $af(n/b) \le cf(n)$ for all $n \ge N$ | $T(n)=\Theta(f(n))$ |
Usage
This theorem gives the asymptotic complexity of divide-and-conquer algorithms directly from their recurrence relation.