Master Theorem

The master theorem is a simple way to obtain an upper bound of the recurrence relation of a divide-and-conquer algorithm, assuming the ‘merging’ step takes polynomial time, and the ‘splitting’ is done with a constant fraction.

Formula §

Master Theorem

$$T(n)=aT(\frac{n}{b})+f(n)\wedge f(n)\in O(n^k)\to T(n)\in \{\begin{array}{ll}\Theta (n^k),& a<b^k\\ \Theta (n^{k}log(n)),& a=b^k\\ \Theta (n^{{\log }_{b}a}),& a>b^k\end{array}$$

Note

• $a\in \mathbb{Z},a\ge 1$ = The amount of subproblems that are used by the algorithm (in the merging step)
• $b\in \mathbb{Z},b>1$ = The factor by which the main problem is divided into.
• $k\ge 0$ = The polynomial factor of n, the additional work done by the algorithm in the merging step
• $f(n)$ = The function representing the merge step

Can $a>b$?

Yes, actually! An algorithm can make use of a sub-solution multiple times, more than the splitting factor. One such example is in Strassen’s Algorithm, where $a=7$ and $b=2$

Limitations §

The Master Theorem, does however, have some limitations:

• Subproblem sizes must be exactly $\frac{n}{b}$
• $f(n)$ must be bounded polynomially $f(n)\in \Theta (n^k)$

It does not work when:

• $f(n)$ grows faster than any polynomial (e.g. $f(n)=2^n$)
• There are uneven splits or non-constant number of subproblems (e.g. $T(n)=T(n/2)+T(n/4)+2n$ )
• Subproblem sizes that are not fractions of $n$

For such cases it is more useful to use Recursion Tree, substitution method (determine closed form + induction proof),#tosee Akra–Bazzi Theorem (generalization of Master Theorem)