Discrete Mathematics for Computer Science

Comparing Growth Rates of Functions 293

Corollary 4: For any integer k > -1 , the polynomial functions in 0(nk) are the polyno-
mial functions of degree less than or equal to k.

We now know that the complexity of any polynomial is completely determined by its
degree. For example, P(n) = n^3 - 3n^2 + n is O(n^3 ), and R(n) = n^3 + 3n is also O(n^3 ).

5.1.4 Exponential and Logarithmic Functions

Before proving some needed facts about the growth rate of the exponential and logarithmic
functions, we need to review some properties of these functions.

Familiar Facts About Exponential and Logarithmic Functions

(a) For m, n, r E l where m, n, r > 0, m < n if and only if mx < x'.
(b) The exponentiation function to a base greater than 1 is an increasing function: For
n,r,s R wheren > landr, s >0,0<r < s if and only if nr <ns.
(c) A logarithmic function to a base greater than 1 is an increasing function: For n, r, s E
R where n > 1 and r, s > 0, r < s if and only if logn(r) < log,(s).
(d) For b, x c R where x > 0, b > 0, and b : 1, 1Ogb(X) = ln(x)/ In(b).
(e) For all m, r, s E R where m > 0, mr+s mr .Ms.
(f) For all m, r, s E R where m > 0, (mr), mrs.
(g) For all m, n, r E R where m, n > 0, log.m(nr) = r logm(n).

We will not prove these facts in this text. Part (c) is equivalent to part (b) since the

functions logn (x) and n', as functions of x, are inverse functions.

The most commonly seen functions that grow faster than the polynomial functions
are the exponential functions. Figure 5.5 shows an example for each of these kinds of
functions.

Y w

1000-

(^800) X WW
600 X ,
x w
400 x
X W
200- x X w
•,• , o•A•,~gdxdwd c Wd d d d d d
2 4 6 8 10
Figure 5.5 n2 (d), n3 (x), and 2n (w).
Theorem 7. Let k E R such that k _> 2. Then:
(a) n k E 0(2n)
(b) 2 n 0 O(nk)