7.6* Deriving the Master theorem

This section is a longer version of Section 7.3.2. Here we show step-by-step how to derive the Master theorem.

There is a general way to solve so called divide-and-conquer recurrence relations. These have the form T(n) = a\cdot T(n/b) + c\cdot n^k, where a, b, c, and k are constants. This recurrence describes a problem of size n divided into a subproblems of size n/b, while c\cdot n^k is the extra work needed to split the input or combine the partial solutions. Both binary search and Mergesort are examples of divide-and-conquer algorithms that fit this form.

To solve a divide-and-conquer recurrence, we do the same as we did before – expand it until we reach the base case:

\begin{align*} T(n) &= a \cdot T(n/b) + c \cdot n^k = a \cdot (a \cdot T(n/b^2) + c \cdot (n/b)^k) + c \cdot n^k \\ &= a \cdot (a \cdot (a \cdot T(n/b^3) + c \cdot (n/b^2)^k) + c \cdot (n/b)^k) + c \cdot n^k \\ &= a \cdot (a \cdot (\cdots (a \cdot (a \cdot T(1) + c \cdot (n/b^{m-1})^k) + c \cdot (n/b^{m-2})^k) \cdots) + c \cdot (n/b)^k) + c \cdot n^k \end{align*}

The recursion stops when we reach T(1), which is after m levels, where n = b^m. Now let’s replace n with b^m and T(1) with c, and then expand the parentheses:

\begin{align*} \cdots &= a \cdot (a \cdot (\cdots (a \cdot (a \cdot c + c \cdot (b^m/b^{m-1})^k) + c \cdot (b^m/b^{m-2})^k) \cdots) + c \cdot (b^m/b)^k) + c \cdot b^{mk} \\ &= a \cdot (a \cdot (\cdots (a \cdot (a \cdot c + c \cdot b^{1k}) + c \cdot b^{2k}) \cdots) + c \cdot b^{(m-1)k}) + c \cdot b^{mk} \\ &= a^m c \cdot b^{0k} + a^{m-1} c \cdot b^{1k} + a^{m-2} c \cdot b^{2k} + \cdots + a^1 c \cdot b^{(m-1)k} + a^0 c \cdot b^{mk} \\ &= c \cdot (a^m b^{0k} + a^{m-1} b^{1k} + a^{m-2} b^{2k} + \cdots + a^1 b^{(m-1)k} + a^0 b^{mk}) \\ &= c \cdot a^m \cdot (b^{0k} / a^0 + b^{1k} / a^1 + b^{2k} / a^2 + \cdots + b^{(m-1)k} / a^{(m-1)} + b^{mk} / a^m) \\ &= c \cdot a^m \cdot \sum^m (b^k/a)^i \\ &= c \cdot a^m \cdot \sum^m r^i, \text{ where } r = b^k / a \text{ and } m = \log_b(n) \end{align*}

The value of \sum^m r^i depends on if r is less than, equal to, or larger than 1:

r < 1 (the subproblems dominate)

The infinite sum \sum r^i converges to 1/(1-r) which is constant, so \sum^m r^i \in O(1). Therefore T(n) \in O(a^m) = O(n^d), because a^m = a^{\log_b(n)} = n^{\log_b(a)} = n^d.

r = 1 (they are comparable)

The sum collapses to \sum^m r^i = \sum^m 1 \in O(m) = O(\log(n)). Furthermore, a = b^k, and so k = \log_b(a). Therefore a^m = n^{\log_b(a)} = n^k, and we get T(n) \in O(n^k \log(n)).

r > 1 (the extra work dominates)

Now the sum becomes \sum^m r^i = (r^{m+1} - 1) / (r - 1) \in O(r^m). Since b^m = n, we get T(n) \in O(a^m r^m) = O(a^m (b^k/a)^m) = O(b^{km}) = O(n^k).

We can summarise the above derivation as the following theorem.