Chapter 4: Recurrences

Overview

As noted in Section 2.3.2, when an algorithm contains a recursive call to itself, its running time can often be described by a recurrence. A recurrence is an equation or inequality that describes a function in terms of its value on smaller inputs. For example, we saw in Section 2.3.2 that the worst-case running time T (n) of the MERGE-SORT procedure could be described by the recurrence

(4.1)

whose solution was claimed to be T (n) = Θ(n lg n).

This chapter offers three methods for solving recurrences-that is, for obtaining asymptotic "Θ" or "O" bounds on the solution. In the substitution method, we guess a bound and then use mathematical induction to prove our guess correct. The recursion-tree method converts the recurrence into a tree whose nodes represent the costs incurred at various levels of the recursion; we use techniques for bounding summations to solve the recurrence. The master method provides bounds for recurrences of the form

T (n) = aT (n/b) + f (n),

where a ≥ 1, b > 1, and f (n) is a given function; it requires memorization of three cases, but once you do that, determining asymptotic bounds for many simple recurrences is easy.