An Introduction to the Analysis of Algorithms, Second Edition

Chapter Two. Recurrence Relations

THE algorithms that we are interested in analyzing normally can be expressed as recursive or iterative procedures, which means that, typically, we can express the cost of solving a particular problem in terms of the cost of solving smaller problems. The most elementary approach to this situation mathematically is to use recurrence relations, as we saw in the quicksort and mergesort analyses in the previous chapter. This represents a way to realize a direct mapping from a recursive representation of a program to a recursive representation of a function describing its properties. There are several other ways to do so, though the same recursive decomposition is at the heart of the matter. As we will see in Chapter ...