Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson and Ronald L. Rivest and Clifford Stein : Chapter 4

In this chapter, the author defines recurrence and provides three methods namely, substitution method, recursion-tree method and and master method to solve recurrences.

The substitution method relies on guessing the solution and then proving it with mathematical induction. The author provides following hints to prove the solution if the mathematical induction doesn't work out:

1. Subtracting a lower order term
2. Change of variables

In a recursion tree, each node represents the cost of a single sub-problem somewhere in the set of recursive function invocations. The sum of costs within each level gives a per-level cost and the sum of all the per-level costs will give the total cost of all levels of the recursion. Recursion tree is used to get the best guess which is then verified by the substitution method. The authors then provide an example of a recurrence relation and derive the solution and prove it using substitution method.

The master method depends on the master theorem which is defined as follows:
Let $ a >= 1 $ and $ b > 1 $ be constants, let $ f(n) $ be a function, and let $ T(n) $ be defined on the non-negative integers by the recurrence
$$ T(n) = a T(n/b) + f(n) $$,
where $ n/b $ is either $ \lfloor n/b \rfloor $ or $ \lceil n/b \rceil $. Then $ T(n) $ can be bounded asymptotically as follows:

1. If $ f(n) = O(n^{\log{_a}b-\sigma}) $ for some constant $ \sigma > 0 $, then $ T(n) = \Theta (n^{\log_ab}) $.
2. If $ f(n) = \Theta(n^{\log{_a}b}) $, then $ T(n) = \Theta (n^{\log{_a}b} \times \lg n) $.
3. If $ f(n) = \Omega(n^{\log{_a}b+\sigma}) $ for some constant $ \sigma > 0 $, and if $ a \times f(n/b) <= c \times f(n) $ for some constant $ c < 1 $ and all sufficiently large $n$, then $ T(n) = \Theta (f(n)) $. The three cases do not cover all the possibilities of $ f(n) $. In case 1, $ f(n) $ must be polynomially smaller than $ n^{\log{_a}b} $ and in case 3, $ f(n) $ must be polynomially larger than $ n^{\log{_a}b} $. Thus if $ f(n) $ is smaller than $ n^{\log{_a}b} $ but not polynomially or if $ f(n) $ is larger than $ n^{\log{_a}b} $ but not polynomially or if the conditions in case 3 does not get satisfied, master method cannot be used to solve the recurrence. The authors then provide examples for each type of case and find solutions. The authors then prove master theorem.