Page 233 - Discrete Mathematics and Its Applications

212 3 / Algorithms

USEFUL BIG-O ESTIMATES INVOLVING LOGARITHMS,POWERS,AND EXPONEN-
TIAL FUNCTIONS We now give some useful facts that help us determine whether big-O
relationships hold between pairs of functions when each of the functions is a power of a loga-
n
rithm, a power, or an exponential function of the form b where b> 1. Their proofs are left as
Exercises 57–60 for readers skilled with calculus.
d
Theorem 1 shows that if f (n) is a polynomial of degree d, then f (n) is O(n ). Applying
c
d
this theorem, we see that if d> c > 1, then n is O(n ). We leave it to the reader to show
that the reverse of this relationship does not hold. Putting these facts together, we see that if
d> c > 1, then
c d d c
n is O(n ), but n is not O(n ).

In Example 7 we showed that log n is O(n) whenever b> 1. More generally, whenever b> 1
b
and c and d are positive, we have
d
d
c
c
(log n) is O(n ), but n is not (O(log n) ).
b b
This tells us that every positive power of the logarithm of n to the base b, where b> 1, is big-O
of every positive power of n, but the reverse relationship never holds.
n
In Example 7, we also showed that n is O(2 ). More generally, whenever d is positive and
b> 1, we have
n
d
n
d
n is O(b ), but b is not O(n ).
This tells us that every power of n is big-O of every exponential function of n with a base
that is greater than one, but the reverse relationship never holds. Furthermore, we have when
c> b> 1,
n n n n
b is O(c ) but c is not O(b ).
This tells us that if we have two exponential functions with different bases greater than one, one
of these functions is big-O of the other if and only if its base is smaller or equal.

The Growth of Combinations of Functions

Many algorithms are made up of two or more separate subprocedures. The number of steps
used by a computer to solve a problem with input of a specified size using such an algorithm is
the sum of the number of steps used by these subprocedures. To give a big-O estimate for the
number of steps needed, it is necessary to find big-O estimates for the number of steps used by
each subprocedure and then combine these estimates.
Big-O estimates of combinations of functions can be provided if care is taken when different
big-O estimates are combined. In particular, it is often necessary to estimate the growth of the
sum and the product of two functions. What can be said if big-O estimates for each of two
functions are known? To see what sort of estimates hold for the sum and the product of two
functions, suppose that f 1 (x) is O(g 1 (x)) and f 2 (x) is O(g 2 (x)).
From the definition of big-O notation, there are constants C 1 , C 2 , k 1 , and k 2 such that

|f 1 (x)|≤ C 1 |g 1 (x)|

when x> k 1 , and

|f 2 (x)|≤ C 2 |g 2 (x)|