Chapter Four. Asymptotic Approximations

Our initial general orientation in the analysis of algorithms is toward deriving exact mathematical results. However, such exact solutions may not be always available, or if available they may be too unwieldy to be of much use. In this chapter, we will examine some methods of deriving approximate solutions to problems or of approximating exact solutions; as a result, we may modify our primary orientation to be toward deriving concise, accurate, and precise estimates of quantities of interest.

In a manner similar to Chapter 3, our primary goal in this chapter is to provide an overview of the basic properties of asymptotic expansions, methods of manipulating them, and a catalog of those that we encounter ...

Get An Introduction to the Analysis of Algorithms, Second Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.