Chapter notes

Recurrences were studied as early as 1202 by L. Fibonacci, for whom the Fibonacci numbers are named. A. De Moivre introduced the method of generating functions (see Problem 4-5) for solving recurrences. The master method is adapted from Bentley, Haken, and Saxe [41], which provides the extended method justified by Exercise 4.4-2. Knuth [182] and Liu [205] show how to solve linear recurrences using the method of generating functions. Purdom and Brown [252] and Graham, Knuth, and Patashnik [132] contain extended discussions of recurrence solving.

Several researchers, including Akra and Bazzi [13], Roura [262], and Verma [306], have given methods for solving more general divide-and-conquer recurrences than are solved by the master method. We describe the result of Akra and Bazzi here, which works for recurrences of the form

where k ≥ 1; all coefficients a_i are positive and sum to at least 1; all b_i are at least 2; f(n) is bounded, positive, and nondecreasing; and for all constants c > 1, there exist constants n₀, d > 0 such that f(n/c) ≥ df (n) for all n ≥ n₀. This method would work on a recurrence such as T(n) = T(⌊n/3⌋) + T(⌊2n/3⌋) + O(n), for which the master method does not apply. To solve the recurrence (4.15), we first find the value of p such that . (Such a p always exists, and it is unique and positive.) The solution to the recurrence is then

for n′ a sufficiently large constant. The Akra-Bazzi method can be somewhat difficult to use, but it serves in solving recurrences that model division of the problem into substantially unequally sized subproblems. The master method is simpler to use, but it applies only when subproblem sizes are equal.