Algorithm analysis - Data Structures and Problem Solving Using Java - page 190

A cubic function is a function whose dominant term is some constant
times . As an example, is a cubic function. Simi-
larly, a quadratic function has a dominant term that is some constant times
, and a linear function has a dominant term that is some constant times N .
The expression represents a function whose dominant term is N
times the logarithm of N . The logarithm is a slowly growing function; for
instance, the logarithm of 1,000,000 (with the typical base 2) is only 20. The
logarithm grows more slowly than a square or cube (or any) root. We discuss
the logarithm in more depth in Section 5.5.

N 3 10 N 3 ++ N 2 40 N + 80

N 2

O ( N log N )

Either of two functions may be smaller than the other at any given point, so
claiming, for instance, that does not make sense. Instead, we mea-
sure the functions' rates of growth. This is justified for three reasons. First, for cubic
functions such as the one shown in Figure 5.2, when N is 1,000 the value of the
cubic function is almost entirely determined by the cubic term. In the function
, for N = 1,000, the value of the function is
10,001,040,080, of which 10,000,000,000 is due to the term. If we were to
use only the cubic term to estimate the entire function, an error of about 0.01 percent
would result. For sufficiently large N , the value of a function is largely determined
by its dominant term (the meaning of the term sufficiently large varies by function).
The second reason we measure the functions' growth rates is that the
exact value of the leading constant of the dominant term is not meaningful
across different machines (although the relative values of the leading constant
for identically growing functions might be). For instance, the quality of the
compiler could have a large influence on the leading constant. The third rea-
son is that small values of N generally are not important. For N = 20,
Figure 5.1 shows that all algorithms terminate within 5 μs. The difference
between the best and worst algorithm is less than a blink of the eye.

The growth rate of
a function is most
important when N
is sufficiently large.

F ( ) G ( ) <

10 N 3 ++ N 2 40 N + 80

10 N 3

We use Big-Oh notation to capture the most dominant term in a function
and to represent the growth rate. For instance, the running time of a quadratic
algorithm is specified as (pronounced “order en-squared”). Big-Oh
notation also allows us to establish a relative order among functions by compar-
ing dominant terms. We discuss Big-Oh notation more formally in Section 5.4.
For small values of N (for instance, those less than 40), Figure 5.1 shows
that one curve may be initially better than another, which doesn't hold for larger
values of N . For example, initially the quadratic curve is better than the
curve, but as N gets sufficiently large, the quadratic algorithm loses
its advantage. For small amounts of input, making comparisons between func-
tions is difficult because leading constants become very significant. The function
N + 2,500 is larger than when N is less than 50. Eventually, the linear func-
tion is always less than the quadratic function. Most important, for small input
sizes the running times are generally inconsequential, so we need not worry
about them. For instance, Figure 5.1 shows that when N is less than 25, all four

Big-Oh notation is
used to capture the
most dominant
term in a function.

ON ( )

O ( N log N )

N 2