Master theorem

Consider a recurrence relation of the following structure.

$$T(n)\le aT\left(\frac{n}{b}\right)+f(n)$$

This equation and its coefficients tells us a lot about the algorithm. Each letter represents a part of how the algorithm works.

• $a$ tells us the number of subproblems we divide into.
• $\frac{n}{b}$ is the size of each of the subproblems. We can have multiple $T\left(\frac{n}{b}\right)$ terms in a single relation.
• $f(n)$ is the time it takes to recombine and/or divide the the subproblems. $f(n)\in O(n)$, and so we can say $f(n)=c_1{n}^d$ for some constant $c_1$ and $d$.

Finally, $T(n)$ would then tell us the overall running time for a size $n$.

Intuition and results

The master theorem tells us about the balance between the number of subproblems (and the size of each), and the time it takes to recombine. They both fight for runtime.

1. $f(n)=n^d\ll n^{{\log }_{b}a}$. In this case, the cost to recombine the subproblems is cheaper than the number of subproblems. Then, $T(n)=O(n^{{\log }_{b}a})$.
2. $f(n)=n^d\gg n^{{\log }_{b}a}$. Here, the cost to recombine is expensive, and will dominate. Therefore, we have $T(n)=O(n^d)$.
3. $f(n)=n^d=n^{{\log }_{b}a}$. Here, the cost of recombining and the size of the subproblems have the “same weight” and one does not dominate the other. Therefore, we can’t ignore either and $T(n)=O(n^d{\log }_{a}n)$.

Proof

Draw a tree. At level $0$, we have one node of size $n$. At level 1, we have $a$ nodes of size $\frac{n}{b}$. At level 2, we have $a^2$ nodes of $\frac{n}{b^2}$, and so on.

The height $h$ of this tree satisfies the equation $\frac{n}{b^h}=1$. Solving this we have $h={\log }_{b}n$. We get the total cost by summing the cost of each level, for each node:

$$T(n)=\sum _{i=0}^h{a}^i\cdot {\left(\frac{n}{b^i}\right)}^d=n^d\sum _{i=0}^h{\left(\frac{a}{b^d}\right)}^i$$

Once again, we can consider the three cases: $a<b^d$, $a=b^d$, and $a=b^d$. The other important part to realize is that the summation we have (after pulling out $n^d$) is a geometric series. This tells us how the summation will evaluate, and which term in the summation will dominate the others.