chapter 5Analysis Tools and Techniques

Remember that time is money.

—Benjamin Franklin (1706–1790)

Time and space are important words in computer science because we want fast algorithms, and we want algorithms that don’t use a lot of memory. The purpose of this chapter is to study some fundamental techniques and tools that can be used to analyze algorithms for the time and space they require. Although the study of algorithm analysis is beyond our scope, we’ll give a brief introduction in the first section to help show the need for the mathematical topics in the rest of the chapter.

The rest of the chapter covers mathematical tools that have applications to the analysis of algorithms. We’ll learn how to find closed forms for sums, as well as ...

Get Discrete Structures, Logic, and Computability, 4th Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.