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 ...