348 ];I Theory of Computer Science
Corollary The order of a polynomial is detennined by its degree.
Defmition 12.2 An exponential function is a function q : N -'7 N defined by
q(n) = a"
for some fixed a > 1.
When n increases, each of n, n". 2" increases. But a comparison of these
functions for specific values of 11 will indicate the vast difference between the
growth rate of these functions.
TABLE 12.1 Growth Rate of Polynomial and Exponential Functions
n
fen) = n
2
g(n) = n
2 + 3n + 9
q(n) = 2"
1
1
13
2
5
25
49
32
10
100
139
1024
50
2500
2659
(113)10
15
100
10000
10309
(1.27)10
30
1000
1000000
1003009
(1.07)10
301
From Table 12.1. it is easy to see that the function q(ll) grows at a very fast
rate when compared to fen) or g(ll). In particular the exponential function
grows at a very fast rate when compared to any polynomial of large degree.
We prove a precise statement comparing the growth rate of polynomials and
exponential function.
Deftnition 12.3 We say g ' * O(j), if for any constant C and No, there exists
n :2: No such that g(l1) > Cf(n).
Definition 12.4 If f and g are two functions and f = O(g), but g ' * O(f),
we say that the growth rate of g is greater than that of.f (In this case
g(n)/f(n) becomes unbounded as 11 increases to 00.)
Theorem 12.2 The growth rate of any exponential function is greater than
that of any polynomial.
Proof Let pen) = ae/ + ak-lnk-1 + . , . + a1n + ao and q(n) = a" for some
a > 1.
As the growth rate of any polynomial is determined by its term with the
highest power, it is enough to prove that Ilk = O(a") and a" ' * O(ll), By
L'Hospital's rule. log 11 tends to 0 as n -'7 00. (Here log n = 10gel1.) If
n
then.
I
(~(n»" = le
(log n 'I
As 11 gets large, k ~-'-l-) tends to 0 and hence ~(Il) tends to O.