In this section we are concerned with determining how fast functions grow and how fast they grow in comparison to one another. For example if we consider the functions f(x) = 2*x + 1 and f2(x) = x² we can plot a table of values comparing x to f1(x) and f2(x).

The table above is quite useful for understanding function growth. Note that as x increases both f1(x) and f2(x) appear to increase at a faster rate than x. However, there is something very different about f1 and f2’s growth. Regardless of what column we look at, f1(x) is always one more than twice x. f2(x), however, is twice x in column 2, 4 times x in column 4 … and 9 times x in column 9. The ratio of f2(x)/x increases with every column.

Let’s compare f1(x) with x as follows. Even though x is always smaller than f1(x) we can find a constant, C, (namely 3) such that f1(x) <= C*x. Because x and f1(x) always differ by less than a constant multiple we consider them to be comparable in growth. However, there is no constant C such that f2(x) <= C*x. Even if we pick a very large constant such as C=1,000,000 we know that if we look at column 1,000,001 f2(x) will be larger than 1,000,000 *x. In fact in column 1,000,001, f2(x) is 1,000,001 times larger than x. Similarly there is no constant C such that f2(x) <= C*f1(x) since the ratio of f2(x)/f1(x) grows larger with every column. Thus, f2 grows at a faster rate than f1.

It is instructional to note that f1(x) is actually larger than f2(x) for columns 1 and 2. However, f2(x) becomes larger in column 3 and becomes increasingly larger in each succeeding column.

Hence, f1(x) <= f2(x) when x > 2.

Big O is used as a rough measure of how fast one function grows with respect to another. We say that function f is big O of function g if and only if f grows no faster than some constant multiple of g. We write this as "f is O(g)." The precise definition of big O as given in your text also accounts for the fact that the larger function may not be larger for the first k columns where k is some constant.

In the example given above we may state correctly that f1(x) is O(x), x is O(f1(x)) and that f1(x) is O(f2(x)). We may not state that f2(x) is O(f1(x)).

1. Compare the functions f1(x) = 100*x² and f2(x) = x³.

2. Compare the functions f1(x) = x and f2(x) = x^1/2

f2(x) is O(f1(x)) since x^1/2 <= x whenever x >= 1.

Theorem 2 and Theorem 3 on page 86 give formulas for O(f + g) and O(f * g). I restate them below.

Theorem 2:

If f1(x) is O(g1(x)) and f2(x) is O(g2(x)) then f1(x) + f2(x) is O(max(g1(x), g2(x)).

Theorem 3:

If f1(x) is O(g1(x)) and f2(x) is O(g2(x)) then f1(x) * f2(x) is O(g1(x)*g2(x))

1. Give a big O estimate for f, where f is x + x^1/2.

2. Give a big O estimate for f, where f is x * x^1/2.

3. Give a big O estimate for the function f(x) = (N² + N*log(N))*(N³ + N + 1)

Therefore f(x) is O(N² * N³)

Therefore by the multiplication rule f(x) is O(N⁵ )

Why big O notation and analyses are important.

The time required for most computer programs to run may usually be determined by a function such as N² or N*log(N) or 2^N, where N represents the size of the program input. For example, some programs which sort data require C1*N² time to run where N is the number of data items to be sorted and C1 is a constant. Other sorting programs require only C2*N*log(N) where N is still the number of data items and C2 is another constant. Let’s observe the running time of two such programs where C1 = 2 and C2 = 10 for various size data sets.

Number of data items

Note that the 2*N² program runs faster for the smallest data sets of size 8 and 16. For all larger data sets listed in the table the 10*N*log(N) program runs faster. And most importantly, the larger the data set the bigger the difference. This knowledge can be very valuable in selecting an algorithm for solving a problem such as sorting numbers. In the example above we might conclude that if the data sets to be sorted contain 25 items or less we should probably opt for the 2* N² program since it is faster in this range of input items and is probably much easier to code.

However, if our data sets tend to be larger than this, say, 2048 data items then it is well worth the effort to employ the more complicated 10*N*log(N) program since it runs almost 40 times faster for data sets of this size. In practice our data sets may consist of many hundreds of thousands of items in which case the slower program could take years or even centuries to complete whereas the faster program might complete in a few hours.

Note that in the table above no actual time units were given. The actual size of the time unit depends upon many factors such as the nature of the data being sorted (for example, byte sized integers as opposed to 1000 byte length strings) and the media on which the data is stored (for example, RAM as opposed to a disk drive). We should always keep in mind the impact of the time required to perform some function in the real world. A factor of 40 may have marginal impact for a real world operation that takes 1 nanosecond as opposed to 40 nanoseconds. However, an operation that takes one second as opposed to 40 seconds would be much more noticeable to a human being who might be waiting for a response from the system.

The following table is useful for getting a feel for the growth of some common functions.

Big O, little O and Theta

Order of Complexity and Function Equivalence Classes