Recursion and Recurrence Functions

Estimating the complexity or running time of iterative algorithms is relatively straightforward due to their linear and predictable nature. However, recursive algorithms, which involve the function calling itself one or more times during execution, present a unique challenge in complexity estimation. These self-referential structures often lead to intricate and non-intuitive running times that cannot be easily discerned through simple observation or traditional iterative analysis.

To address this challenge, we introduce the concept of recurrence functions. Recurrence functions are mathematical models that describe the running time of a recursive algorithm in terms of its input size. By expressing the running time as a function that recurs upon itself, we can systematically analyze and solve these recurrences to obtain a precise estimate of the algorithm’s complexity.

This chapter explores the various aspects of recurrence functions, including...