Page 237 - Discrete Mathematics and Its Applications

216 3 / Algorithms

One useful fact is that the leading term of a polynomial determines its order. For example,
5
4
3
5
if f(x) = 3x + x + 17x + 2, then f(x) is of order x . This is stated in Theorem 4, whose
proof is left as Exercise 50.
n
THEOREM 4 Let f(x) = a n x + a n−1 x n−1 + ··· + a 1 x + a 0 , where a 0 ,a 1 ,...,a n are real numbers with
n
a n = 0. Then f(x) is of order x .

4
2
8
7
EXAMPLE 13 The polynomials 3x + 10x + 221x + 1444, x 19 − 18x − 10,112, and −x 99 + 40,001x 98
99
8
19
+ 100,003x are of orders x , x , and x , respectively. ▲
Unfortunately, as Knuth observed, big-O notation is often used by careless writers and
speakers as if it had the same meaning as big-Theta notation. Keep this in mind when you see
big-O notation used. The recent trend has been to use big-Theta notation whenever both upper
and lower bounds on the size of a function are needed.
Exercises

2
2
In Exercises 1–14, to establish a big-O relationship, find wit- 12. Show that x log x is O(x ) but that x is not O(x log x).
n
n
n
n
nesses C and k such that |f(x)|≤ C|g(x)| whenever x> k. 13. Show that 2 is O(3 ) but that 3 is not O(2 ). (Note that
this is a special case of Exercise 60.)
1. Determine whether each of these functions is O(x). 3
14. Determine whether x is O(g(x)) for each of these func-
a) f(x) = 10 b) f(x) = 3x + 7 tions g(x).
2
c) f(x) = x + x + 1 d) f(x) = 5 log x 2 3
a) g(x) = x b) g(x) = x
2
2
e) f(x) = x f) f(x) = x/2 c) g(x) = x + x 3 d) g(x) = x + x 4
3
2
2. Determine whether each of these functions is O(x ). e) g(x) = 3 x f) g(x) = x /2
2
a) f(x) = 17x + 11 b) f(x) = x + 1000 15. Explain what it means for a function to be O(1).
2
4
c) f(x) = x log x d) f(x) = x /2 16. Show that if f(x) is O(x), then f(x) is O(x ).
e) f(x) = 2 x f) f(x) = x ·Ðx 17. Suppose that f(x), g(x), and h(x) are functions such that
3. Use the definition of “f(x) is O(g(x))” to show that f(x) is O(g(x)) and g(x) is O(h(x)). Show that f(x) is
3
4
4
x + 9x + 4x + 7is O(x ). O(h(x)).
k
k
18. Let k be a positive integer. Show that 1 + 2 + ···+ n k
4. Use the definition of “f(x) is O(g(x))” to show that k+1
x
x
2 + 17 is O(3 ). is O(n ).
19. Determine whether each of the functions 2 n+1 and 2 2n is
2
5. Show that (x + 1)/(x + 1) is O(x). n
O(2 ).
3
2
6. Show that (x + 2x)/(2x + 1) is O(x ). 20. Determine whether each of the functions log(n + 1) and
n
2
7. Find the least integer n such that f(x) is O(x ) for each log(n + 1) is O(log n).
√
n
n
of these functions. 21. Arrange the functions n, 1000 log n, n log n,2n!,2 ,3 ,
2
3
2
a) f(x) = 2x + x log x and n /1,000,000 in a list so that each function is big-O
3
b) f(x) = 3x + (log x) 4 of the next function. √
3
n
4
3
2
n
c) f(x) = (x + x + 1)/(x + 1) 22. Arrange the function (1.5) , n 100 , (log n) , n log n,10 ,
2
98
4
4
d) f(x) = (x + 5 log x)/(x + 1) (n!) , and n 99 + n in a list so that each function is big-O
n
8. Find the least integer n such that f(x) is O(x ) for each of the next function.
of these functions. 23. Suppose that you have two different algorithms for solv-
3
2
a) f(x) = 2x + x log x ing a problem. To solve a problem of size n, the first
5
b) f(x) = 3x + (log x) 4 algorithm uses exactly n(log n) operations and the sec-
3/2
4
4
2
c) f(x) = (x + x + 1)/(x + 1) ond algorithm uses exactly n operations. As n grows,
3
4
d) f(x) = (x + 5 log x)/(x + 1) which algorithm uses fewer operations?
24. Suppose that you have two different algorithms for solv-
2
3
3
9. Show that x + 4x + 17 is O(x ) but that x is not ing a problem. To solve a problem of size n, the first
2
O(x + 4x + 17). 2 n
algorithm uses exactly n 2 operations and the second
3
3
4
4
10. Show that x is O(x ) but that x is not O(x ). algorithm uses exactly n! operations. As n grows, which
4
4
4
4
11. Show that 3x + 1is O(x /2) and x /2is O(3x + 1). algorithm uses fewer operations?