The Algorithm Design Manual Second Edition

4.10.1

Recurrence Relations

Many divide-and-conquer algorithms have time complexities that are naturally

modeled by recurrence relations. Evaluating such recurrences is important to un-

derstanding when divide-and-conquer algorithms perform well, and provide an im-

portant tool for analysis in general. The reader who balks at the very idea of

analysis is free to skip this section, but there are important insights into design

that come from an understanding of the behavior of recurrence relations.

What is a recurrence relation? It is an equation that is defined in terms of itself.

The Fibonacci numbers are described by the recurrence relation F

n

= F

n

−1

+ F

n

−2

and discussed in Section

8.1.1.

Many other natural functions are easily expressed

as recurrences. Any polynomial can be represented by a recurrence, such as the

linear function:

a

n

= a

n

−1

+ 1, a

1

= 1

−→ a

n

= n

---

136

4 .

S O R T I N G A N D S E A R C H I N G

Any exponential can be represented by a recurrence:

a

n

= 2a

n

−1

, a

1

= 1

−→ a

n

= 2

n

−1

Finally, lots of weird functions that cannot be described easily with conventional

notation can be represented by a recurrence:

a

n

= na

n

−1

, a

1

= 1

−→ a

n

= n!

This means that recurrence relations are a very versatile way to represent functions.

The self-reference property of recurrence relations is shared with recursive pro-

grams or algorithms, as the shared roots of both terms reflect. Essentially, recur-

rence relations provide a way to analyze recursive structures, such as algorithms.