``Master Theorem'' - Revised Version

Let

$$T(n) = \cases{ a T(n/b) + c n^d & $n > 1$\ \cr f & $n = 1$}$$

where $n = b^k$.

Then

$$T(n) = \cases{ \left(f + \frac{c}{\frac{a}{b^d} - 1}\right) ... ... $} \cr n^d(f + c\log_b n) = \Theta(n^d\log_b n) & $a = b^d$}.$$

Proof:

$$\begin{eqnarray*} T(n) & = & aT(\frac{n}{b}) + cn^d \\ & = & a \left[ aT(\frac{... ...& f n^{\log_b a} + c \frac{n^d - n^{\log_b a}}{1- \frac{a}{b^d}} \end{eqnarray*}$$

If $\frac{a}{b^d} = 1$ then

$$\begin{eqnarray*} T(n) & = & a^k T(\frac{n}{b^k}) + cn^d \sum_{j=0}^{k-1} (\frac... ...^k$\ or $k = \log_b n$} \\ & = & f n^{\log_b a} + cn^d \log_b n \end{eqnarray*}$$

$\Box$

Intuition: The solution of this recurrence can be thought of in terms of a tree, where the root contributes $cn^d$ and has $a$ children. Each child contributes $c(\frac{n}{b})^d$ and has $a$ children. Each grandchild contributes $c(\frac{n}{b^2})^d$ and has $a$ children. Etc. The tree has height $\log_b n$, and there are $n^{\log_b a}$ leaves.

$\bullet$

When the branching factor is high ($a > b^d$), a major portion of the contribution occurs at the leaves. This yields $\Theta(n^{\log_b a})$.

$\bullet$

When the branching factor is low ($a < b^d$), a major portion of the contribution occurs at the root. This yields $\Theta(n^d)$.

$\bullet$

When the branching factor is ``in between'' ($a = b^d$), each nonleaf level of the tree contributes the same amount. There are $\log_b n$ nonleaf levels each of which contributes $cn^d$. The $n^d$ leaves each contribute $f$. The total is $n^d(f + c\log_b n)$.

Summing solutions: If

$$T(n) = \cases{ a T(n/b) + \sum c_i n^{d_i} & $n > 1$\ \cr f & $n = 1$}$$

then we can just sum the solutions of each recurrence:

$$T_i(n) = \cases{ a T_i(n/b) + c_i n^{d_i} & $n > 1$\ \cr 0 & $n = 1$}$$

and add in $fn^{\log_ba}$ for the contribution from the leaves. For example, MergeSort has the following recurrence:

$$T(n) = \cases{ 2 T(n/2) + n - 1 & $n > 1$\ \cr 0 & $n = 1$}$$

The $+n$ term gives a solution of $n \lg n$, the $-1$ term gives a solution of $-n+1$, and the leaves contribute $0 \cdot n^{\log_2 2}$, so the full solution is

$$T(n) ~~=~~ n \lg n - n + 1$$