Methods in Algorithmic Analysis

Chapter 10

Introduction to Asymptotics

The results of analyses of algorithms are rarely given by closed-form expressions. Usually,

we get a difficult sum or integral. Even when we are lucky or resourceful, and derive closed-

form results, they tend to be hard to use; the formulas are too complicated to “see through”

and get insight into the dependence of the algorithm performance on the parameters.

Sometimes we can derive a formula for the answer to a problem and yet be unable to eval-

uate it numerically because the number crunching simply becomes overwhelming. Modern

computers have come a long way to make such concerns far less serious than they once were.

Nevertheless, computers fail to solve problems involving vast operations and we are forced

to find another approach to overcome this obstacle.

Nearly always, a typical problem in analysis of an algorithm contains a large parameter that

represents the problem size. When the problem size is small, the performance issues are of

small interest—even a poor algorithm delivers the goods. The relative quality of algorithms

is judged by their handling large problems, w here the differences between the good and the

bad can be staggering. Therefore, the context of the present treatment is real-valued (positive)

functions depending on a positive parameter, and the main interest is to determine the behav-

ior of the functions for large values of this parameter. We plan to produce approximations,

in a sense we shall see below, which is called asymptotic. The word

asymptotic

stems from

a Greek expression meaning ”not meeting,” and is associated with the image of a function

approaching, but not reaching (or meeting) a limit as its argument increases. Those unmet

lines are called asymptotes.

This chapter contains many methods and techniques to obtain and analyze asymptotic be-

havior of different expressions involved. Insights into the character of random phenomena

are customary obtained by looking at the asymptotic distributions of the random variables

discussed (which is the topic of §10.7).

Deriving asymptotic formulas usually require a solid mathematical background and good

knowledge about many intermediate steps. Understanding impossibility to present all details,

we use many results without proofs (but giving a reference) and then show other derivations.

545