Algorithms in a Nutshell

Rate of Growth of Functions

The widely accepted method for describing the behavior of an algorithm is to represent the rate of growth of its execution time as a function of the size of the input problem instance. Characterizing an algorithm's performance in this way is an abstraction that ignores details. To use this measure properly requires an awareness of the details hidden by the abstraction.

Every program is run on a platform, which is a general term meant to encompass:

• The computer on which the program is run, its CPU, data cache, floating-point unit (FPU), and other on-chip features

• The programming language in which the program is written, along with the compiler/interpreter and optimization settings for generated code

• The operating system

• Other processes being run in the background

One underlying assumption is that changing any of the parameters comprising a platform will change the execution time of the program by a constant factor. To place this discussion in context, we briefly discuss the Sequential Search algorithm, presented later in Chapter 5. Sequential Search examines a list of n≥1 distinct elements, one at a time, until a desired value, v, is found. For now, assume that:

• There are n distinct elements in the list

• The element being sought, v, is in the list

• Each element in the list is equally likely to be the value v

To understand the performance of Sequential Search, we must know how many elements it examines "on average." Since v is known to be in the list and each element ...