Master Theorem

The master theorem provides a solution to recurrence relations of the form

$$T(n) = a T\left(\frac nb\right) + f(n),$$

for constants $a \geq 1$ and $b > 1$ with $f$ asymptotically positive. Such recurrences occur frequently in the runtime analysis of many commonly encountered algorithms.

Many algorithms have a runtime of the form

$$T(n) = a T\left(\frac nb\right) + f(n),$$

where $n$ is the size of the input and $a \, (\geq 1)$ and $b \,( > 1)$ are constants with $f$ asymptotically positive. For instance, one can show that runtime of the merge sort algorithm satisfies

$$T(n) = 2T\left(\frac n2\right) + n.$$

Similarly, traversing a binary tree takes time

$$T(n) = 2 T\left(\frac n2\right) + O(1).$$

By comparing $\log_b{a}$ to the asymptotic behavior of $f(n)$, the master theorem provides a solution to many frequently seen recurrences.

First, consider an algorithm with a recurrence of the form

$$T(n) = a T\left(\frac nb\right),$$

where $a$ represents the number of children each node has, and the runtime of each of the three initial nodes is the runtime of $T\left(\frac nb\right)$.

The tree has a depth of $\log _b n$ and depth $i$ contains $a^i$ nodes. So there are $a ^ {\log _b n} = n ^ {\log _b a}$ leaves, and hence the runtime is $\Theta\left(n^{\log_b{a}}\right)$.

Intuitively, the master theorem argues that if an asymptotically positive function $f$ is added to the recurrence so that one instead has

$$T(n) = a T\left(\frac nb\right) + f(n),$$

it is possible to determine the asymptotic form of $T$ based on a relative comparison between $f$ and $n^{\log_b{a}}$.

Master Theorem

Given a recurrence of the form

$$T(n) = a T\left(\frac nb\right) + f(n),$$

for constants $a\,( \geq 1)$ ) and $b\,( > 1)$ with $f$ asymptotically positive, the following statements are true:

• Case 1. If $f(n) = O\left(n^{\log_b{a} - \epsilon}\right)$ for some $\epsilon > 0$, then $T(n) = \Theta\left(n^{\log_b{a}}\right)$.

• Case 2. If $f(n) = \Theta\left(n^{\log_b{a}}\right)$, then $T(n) = \Theta\left(n^{\log_b{a}} \log{n} \right)$.

• Case 3. If $f(n) = \Omega\left(n^{\log_b{a} + \epsilon}\right)$ for some $\epsilon > 0$ $\big($and $af\big(\frac nb\big) \leq c f(n)$ for some $c < 1$ for all $n$ sufficiently large$\big),$ then $T(n) = \Theta\big(f(n)\big)$.

Simply put, if $f(n)$ is polynomially smaller than $n^{\log_b{a}}$, then $n^{\log_b{a}}$ dominates, and the runtime is $\Theta\left(n^{\log_b{a}}\right)$. If $f(n)$ is instead polynomially larger than $n^{\log_b{a}}$, then $f(n)$ dominates, and the runtime is $\Theta\big(f(n)\big)$. Finally, if $f(n)$ and $n^{\log_b{a}}$ are asymptotically the same, then $T(n) = \Theta\left(n^{\log_b{a}} \log{n} \right)$.

Note that the master theorem does not provide a solution for all $f$. In particular, if $f$ is smaller or larger than $n^{\log_b{a}}$ by less than a polynomial factor, then none of the three cases are satisfied. For instance, consider the recurrence

$$T(n) = 3 T\left(\frac n3\right) + n \log{n}.$$

In this case, $n^{\log_b{a}} = n$. While $f$ is asymptotically larger than $n$, it is larger only by a logarithmic factor; it is not the case that $f(n) = O\left(n^{\log_b{a} - \epsilon}\right)$ for some $\epsilon > 0$. Therefore, the master theorem makes no claim about the solution to this recurrence.

As mentioned in the introduction, the mergesort algorithm has runtime

$$T(n) = 2T\left(\frac n2\right) + n.$$

$n^{\log_b{a}} = n$ and $f(n) = n$, so case 2 of the master theorem gives $T(n) = \Theta\left(n^{\log_b{a}} \log{n} \right) = \Theta\left(n \log{n}\right)$.

Similarly, as mentioned before, traversing a binary tree takes time

$$T(n) = 2 T\left(\frac n2\right) + O(1).$$

$n^{\log_b{a}} = n$, which is asymptotically larger than a constant factor, so case 1 of the master theorem gives $T(n) = \Theta\left(n^{\log_b{a}}\right) = \Theta\left(n\right)$.

Consider the recurrence

$$T(n) = 9 T\left(\frac n3\right) + n.$$

In this case, $n^{\log_b{a}} = n^2$ and $f(n) = n$. Since $f(n)$ is polynomially smaller than $n^{\log_b{a}}$, case 1 of the master theorem implies that $T(n) = \Theta\left(n^2\right)$.

Consider the recurrence

$$T(n) = 27 T\left(\frac n3\right) + n^3.$$

In this case, $n^{\log_b{a}} = n^3$ and $f(n) = n^3$. Since $f(n)$ is asymptotically the same as $n^{\log_b{a}}$, case 2 of the master theorem implies that $T(n) = \Theta\left(n^3 \log{n} \right)$.

Consider the recurrence

$$T(n) = 2 T\left(\frac n2\right) + n^2.$$

In this case, $n^{\log_b{a}} = n$ and $f(n) = n^2$. Since $f(n)$ is asymptotically larger than $n^{\log_b{a}}$, case 3 of the master theorem asks us to check whether $af\left(\frac nb\right) \leq c f(n)$ for some $c < 1$ and all $n$ sufficiently large. This is indeed the case, so $T(n) = \Theta\big(f(n)\big) = \Theta\left( n^2 \right)$.

Consider the recurrence

$$T(n) = 8 T\left(\frac n2\right) + \frac{n^3}{\log{n}}.$$

In this case, $n^{\log_b{a}} = n^3$ and $f(n) = \frac{n^3}{\log{n}}$. $f(n)$ is smaller than $n^{\log_b{a}}$ but by less than a polynomial factor. Therefore, the master theorem makes no claim about the solution to the recurrence.

• Merge Sort

• Binary Tree

[1] Cormen, T.H., et al. Introduction to Algorithms. MIT Press, 2009.