The master method is commonly used to evaluate [[algorithmic efficiency]] for algorithms that use [[base/Algorithms/recursion|recursion]]. To use the master method, first express the [[recurrence]] of the algorithm in the form $T(n) = \begin{cases} \Theta(1) \text{ if } n\le 1 \\ a T \Big (\frac{n}{b} \Big) + \Theta(n^c) \end{cases} $ Next simply lookup the correct runtime from the table below where $\epsilon = log_b a$. | Case | Runtime | | -------------- | ----------------------------- | | $\epsilon > c$ | $\Theta(n^{\epsilon})$ | | $\epsilon = c$ | $\Theta(n^{\epsilon} \lg n)$) | | $\epsilon < c$ | $\Theta(n^c)$ |