A general recurrence relation solution formula. It’s a generalization of the “tree” method in example 1. intuition Every Recursion Theorem problem has a struggle between most work sitting at the “bottom” of the tree (number of subproblems explode, a > b^{d}) vs most work sitting at the “top” of the tree (problem lower in the tree are smaller, a < b^{d}). constituents Consider: a: number of subproblems b: input size shrink d need to do n^{d} work to merge subproblems Suppose a \geq 1, b> 1, and d are constants. Suppose T\left(n\right) = aT\left(\frac{n}{b}\right) + O\left(n^{d}\right), we then have: requirements \begin{equation} T\left(n\right) = \begin{cases} O\left(n^{d}\log\left(n\right)\right), \text{ if } a = b^{d}\ O\left(n^{d}\right), \text{ if } a < b^{d}\ O\left(n^{\log_{b} \left(a\right)}\right), \text{ if } a > b^{d}\ \end{cases} \end{equation} additional information proof Suppose that T\left(n\right) \leq a\cdot T\left(\frac{n}{b}\right) + c \cdot n^{d}. We desire the master theorem’s statement. Consider a standard tree argument via merge sort. At each layer, the input size gets cut by b, so we obtain \log_{b} \left(n\right) layers of the tree. Filling things out we get the following table: Adding up the work of this table:
The master theorem therefore splits equation into three components based on the ratio \frac{a}{b^{d}}: a = b^{d} So we obtain:
a < b^{d} Recall bounded geometric sum. Notice that if a < b^{t}, then \left(\frac{a}{b^{d}}\right)^{t} should be x^{t}, x< 1, so its bounded by a constant. Hence:
a > b^{d} by bounded geometric sum