The Definition of ``on the Order of''

It is time to introduce a rigorous description of the phrase ``on the order of'' and to explain why it is acceptable to ignore some constants. Any serious programmer must be thoroughly familiar with this notion. It is the most fundamental method for analyzing and comparing the behavior of programs. This intermezzo provides a first glimpse at the idea; a second course on computing usually provides some more in-depth considerations.

.5pt Figure: A comparison of two running time expressions

Let's consider a sample ``order of'' claim with concrete examples before we agree on a definition. Recall that a function F may require on the order of N steps and a function G steps, even though both compute the same results for the same inputs. Now suppose the basic time constants are 1000 for F and 1 for G. One way to compare the two claims is to tabulate the abstract running time:

At first glance the table seems to say that G's performance is better than F's, because for inputs of the same size (N), G's running time is always smaller than F's. But a closer look reveals that as the inputs get larger, G's advantage decreases. Indeed, for an input of size 1000, the two functions need the same number of steps, and thereafter G is always slower than F. Figure  compares the graphs of the two expressions. It shows that the linear graph for dominates the curve of for some finite number of points but thereafter it is below the curve.

The concrete example recalls two important facts about our informal discussion of abstract running time. First, our abstract description is always a claim about the relationship between two quantities: the size of the input and the number of natural recursions evaluated. More precisely, the relationship is a (mathematical) function that maps an abstract size measure of the input to an abstract measure of the running time. Second, when we compare ``on the order of'' properties of functions, such as

we really mean to compare the corresponding functions that consume N and produce the above results. In short, a statement concerning the order of things compares two functions on natural numbers (N).

The comparison of functions on N is difficult because they are infinite. If a function f produces larger outputs than some other function g for all natural numbers, then f is clearly larger than g. But what if this comparison fails for just a few inputs? Or for 1,000 such as the one illustrated in figure ? Because we would still like to make approximate judgments, programmers and scientists adapt the mathematical notion of comparing functions up to some factor and some finite number of exceptions.

ORDER-OF (BIG-O): Given a function g on the natural numbers, O(g) (pronounced: ``big-O of g'') is a class of functions on natural numbers. A function f is in O(g) if there exist numbers c and bigEnough such that for all , it is true that

Recall the performance of F and G above. For the first, we assumed that it consumed time according to the following function

the performance of second one obeyed the function g:

Using the definition of big-O, we can say that f is O(g), because for all ,

which means and c = 1.

More important, the definition of big-O provides us with a shorthand for stating claims about a functions running time. For example, from now on, we say how-many's running time is O(N). Keep in mind that N is the standard abbreviation of the (mathematical) function g(N) = N. Similarly, we can say that, in the worst case, sort's running time is and max's is .

Finally, the definition of big-O explains why we don't have to pay attention to specific constants in our comparsions of abstract running time. Consider max and max2. We know that max's worst-case running time is in , max2's is in O(N). Say, we need the maximum of a list with 10 numbers. Assuming max and max2 roughly consume the same amount of time per basic step, max will need steps and max2 will need 10 steps, which means max2 will be faster. Now even if max2's basic step requires twice as much time as max's basic step, max2 is still around 50 times faster. Futhermore, if we double the size of the input list, max's apparent disadvantage totally disappears. In general, the larger the input is, the less relevant are the specific constants.

Exercise 29.2.1

In the first subsection, we stated that the function belongs to the class . Determine the pair of numbers c and bigEnough that verify this claim. Solution

Exercise 29.2.2

Consider the functions and . Show that g belongs to O(f), which means that f is abstractly speaking more (or at least equally) expensive than g. If the input size is guaranteed to be between 3 and 12, which function is better? Solution

Exercise 29.2.3

Compare and . Does f belong to O(g) and/or g to O(f)? Solution