Page 230 - Discrete Mathematics and Its Applications

3.2 The Growth of Functions 209

3
3
2
2
the relationship 7x is O(x ). Alternatively, when x> 1, we have 7x < 7x , so that C = 7
2
3
and k = 1 are also witnesses to the relationship 7x is O(x ). ▲
Example 3 illustrates how to show that a big-O relationship does not hold.
2
EXAMPLE 3 Show that n is not O(n).
2
Solution: To show that n is not O(n), we must show that no pair of witnesses C and k exist
2
such that n ≤ Cn whenever n>k. We will use a proof by contradiction to show this.
2
Suppose that there are constants C and k for which n ≤ Cn whenever n>k. Observe that
2
when n> 0 we can divide both sides of the inequality n ≤ Cn by n to obtain the equivalent
inequality n ≤ C. However, no matter what C and k are, the inequality n ≤ C cannot hold for
all n with n>k. In particular, once we set a value of k, we see that when n is larger than the
maximum of k and C, it is not true that n ≤ C even though n>k. This contradiction shows
2
that n in not O(n). ▲

2
2
3
3
EXAMPLE 4 Example 2 shows that 7x is O(x ). Is it also true that x is O(7x )?
2
3
Solution: To determine whether x is O(7x ), we need to determine whether witnesses C and
3
2
k exist, so that x ≤ C(7x ) whenever x> k. We will show that no such witnesses exist using
a proof by contradiction.
2
3
If C and k are witnesses, the inequality x ≤ C(7x ) holds for all x> k. Observe that the
2
3
inequality x ≤ C(7x ) is equivalent to the inequality x ≤ 7C, which follows by dividing both
2
sides by the positive quantity x . However, no matter what C is, it is not the case that x ≤ 7C
for all x> k no matter what k is, because x can be made arbitrarily large. It follows that no
3
2
witnesses C and k exist for this proposed big-O relationship. Hence, x is not O(7x ). ▲
Big-O Estimates for Some Important Functions
Polynomials can often be used to estimate the growth of functions. Instead of analyzing the
growth of polynomials each time they occur, we would like a result that can always be used to
estimate the growth of a polynomial. Theorem 1 does this. It shows that the leading term of a
n
polynomial dominates its growth by asserting that a polynomial of degree n or less is O(x ).
n
THEOREM 1 Let f(x) = a n x + a n−1 x n−1 + ··· + a 1 x + a 0 , where a 0 ,a 1 ,...,a n−1 ,a n are real num-
n
bers. Then f(x) is O(x ).

Proof: Using the triangle inequality (see Exercise 7 in Section 1.8), if x> 1wehave
n
|f(x)|=|a n x + a n−1 x n−1 + ··· + a 1 x + a 0 |
n
≤|a n |x +|a n−1 |x n−1 +· · ·+|a 1 |x +|a 0 |
= x n |a n |+|a n−1 |/x +· · ·+|a 1 |/x n−1 +|a 0 |/x n
n
≤ x (|a n |+|a n−1 |+· · ·+|a 1 |+|a 0 |) .
This shows that

n
|f(x)|≤ Cx ,