Definition
Master’s theorem is a theorem that uses for algorithm analysis.
Formal theorem
Let $a \ge 1$ and $b \ge 1$ be constants, $f(n)$ be a non negative function and $T(n)$ be a function defined on the nonnegative intergers by the recurrence $T(n) = aT(n/b) + f(n)$ along with sufficient base cases, where we interpret $n/b$ to mean either $ceil(n/b)$ or $floor(n/b)$.
| 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))$ |
Meaning
This theorem can let us know about the complexity of an algorithm when it uses Divide and conquer approach.