Page 231 - Discrete Mathematics and Its Applications

210 3 / Algorithms

where C =|a n |+|a n−1 |+· · ·+|a 0 | whenever x> 1. Hence, the witnesses C =|a n |+|a n−1 |
n
+··· + |a 0 | and k = 1 show that f(x) is O(x ).
We now give some examples involving functions that have the set of positive integers as
their domains.

EXAMPLE 5 How can big-O notation be used to estimate the sum of the first n positive integers?

Solution: Because each of the integers in the sum of the first n positive integers does not exceed
n, it follows that

2
1 + 2 + ··· + n ≤ n + n + ··· + n = n .
2
From this inequality it follows that 1 + 2 + 3 + ··· + n is O(n ), taking C = 1 and k = 1as
witnesses. (In this example the domains of the functions in the big-O relationship are the set of
positive integers.) ▲

In Example 6 big-O estimates will be developed for the factorial function and its loga-
rithm. These estimates will be important in the analysis of the number of steps used in sorting
procedures.

EXAMPLE 6 Give big-O estimates for the factorial function and the logarithm of the factorial function, where
the factorial function f (n) = n! is defined by

n!= 1 · 2 · 3 · ··· · n

whenever n is a positive integer, and 0!= 1. For example,

1!= 1, 2!= 1 · 2 = 2, 3!= 1 · 2 · 3 = 6, 4!= 1 · 2 · 3 · 4 = 24.

Note that the function n! grows rapidly. For instance,

20!= 2,432,902,008,176,640,000.

Solution: A big-O estimate for n! can be obtained by noting that each term in the product does
not exceed n. Hence,

n!= 1 · 2 · 3 · ··· · n
≤ n · n · n · ··· · n
n
= n .

n
This inequality shows that n! is O(n ), taking C = 1 and k = 1 as witnesses. Taking logarithms
of both sides of the inequality established for n!, we obtain

n
log n!≤ log n = n log n.
This implies that log n! is O(n log n), again taking C = 1 and k = 1 as witnesses. ▲