Page 232 - Discrete Mathematics and Its Applications

3.2 The Growth of Functions 211

n
EXAMPLE 7 In Section 4.1, we will show that n< 2 whenever n is a positive integer. Show that this
n
inequality implies that n is O(2 ), and use this inequality to show that log n is O(n).
n n
Solution: Using the inequality n< 2 , we quickly can conclude that n is O(2 ) by taking k =
C = 1 as witnesses. Note that because the logarithm function is increasing, taking logarithms
(base 2) of both sides of this inequality shows that

log n<n.

It follows that
log n is O(n).

(Again we take C = k = 1 as witnesses.)
If we have logarithms to a base b, where b is different from 2, we still have log n is O(n)
b
because
log n n
log n = <
b
log b log b
whenever n is a positive integer. We take C = 1/ log b and k = 1 as witnesses. (We have used
Theorem 3 in Appendix 2 to see that log n = log n/ log b.) ▲
b
As mentioned before, big-O notation is used to estimate the number of operations needed to
solve a problem using a specified procedure or algorithm. The functions used in these estimates
often include the following:

2 n
1, log n, n, n log n, n , 2 ,n!
Using calculus it can be shown that each function in the list is smaller than the succeeding
function, in the sense that the ratio of a function and the succeeding function tends to zero
as n grows without bound. Figure 3 displays the graphs of these functions, using a scale for
the values of the functions that doubles for each successive marking on the graph. That is, the
vertical scale in this graph is logarithmic.

n!
4096
2048
1024
512 n
2
256
128
n 2
64
32
n log n
16
n
8
4 log n
2
l
1
2 3 4 5 6 7 8

FIGURE 3 A Display of the Growth of Functions Commonly Used in Big-O Estimates.