Introduction to Recursive Programming

CHAPTER 3

Runtime Analysis of Recursive Algorithms

The faster you go, the shorter you are.

—Albert Einstein

ALGORITHM analysis is the field that studies how to theoretically estimate the resources that algorithms need in order to solve computational problems. This chapter focuses on analyzing the runtime, also denoted as “computational time complexity,” of recursive algorithms that solve problems whose size depends on a single factor (which occurs in the majority of the problems covered in the book). This will provide a context that will enable us to characterize and compare different algorithms regarding their efficiency. In particular, the chapter describes two methods for solving recurrence relations, which are recursive mathematical ...