Master Theorem

See Also:

• Recursion
• Divide-and-Conquer

The master theorem is a simple way to obtain the time complexity of a Divide-and-Conquer algorithm from it’s recurrence relation

Formula §

If $T(n)=\{\begin{array}{ll}aT(\frac{n}{b})+n^k,& n>1\\ d,& n=1\end{array}$ where

• $a$ = The amount of subproblems that are used by the algorithm.
• $b$ = The factor by which the n problem is divided into.
• $k$ = The polynomial factor of n, the additional work done by the algorithm then:

$T(n)=\{\begin{array}{ll}O(n^k),& a<b^k\\ O(n^{k}log(n)),& a=b^k\\ O(n^{{\log }_{b}a}),& a>b^k\end{array}$

For example, take the example of a divide-and-conquer algorithm, mergesort. The recursion tree of mergesort is as follows: