Page 238 - Discrete Mathematics and Its Applications

3.2 The Growth of Functions 217

25. Give as good a big-O estimate as possible for each of 39. Show that if f and g are real-valued functions such that
n
these functions. f(x) is O(g(x)), then for every positive integer n, f (x)
n
n
n
2
3
2
a) (n + 8)(n + 1) b) (n log n + n )(n + 2) is O(g (x)). [Note that f (x) = f(x) .]
3
2
n
c) (n!+ 2 )(n + log(n + 1)) 40. Show that for all real numbers a and b with a> 1 and
b> 1, if f(x) is O(log x), then f(x) is O(log x).
26. Give a big-O estimate for each of these functions. For the b a
function g in your estimate f(x) is O(g(x)), use a simple 41. Suppose that f(x) is O(g(x)) where f and g are in-
function g of smallest order. creasing and unbounded functions. Show that log |f(x)|
3
3
2
a) (n +n log n)(log n+1) + (17 log n+19)(n +2) is O(log |g(x)|).
42. Suppose that f(x) is O(g(x)). Does it follow that 2 f(x)
n
n
2
3
b) (2 + n )(n + 3 ) g(x)
is O(2 )?
n
n
n
n
c) (n + n2 + 5 )(n!+ 5 )
43. Let f 1 (x) and f 2 (x) be functions from the set of real
27. Give a big-O estimate for each of these functions. For the numbers to the set of positive real numbers. Show that if
function g in your estimate that f(x) is O(g(x)), use a
f 1 (x) and f 2 (x) are both (g(x)), where g(x) is a func-
simple function g of the smallest order.
tion from the set of real numbers to the set of positive real
2
2
a) n log(n + 1) + n log n numbers, then f 1 (x) + f 2 (x) is (g(x)). Is this still true
2
2
b) (n log n + 1) + (log n + 1)(n + 1) if f 1 (x) and f 2 (x) can take negative values?
c) n 2 n + n n 2 44. Suppose that f(x), g(x), and h(x) are functions such that
f(x) is (g(x)) and g(x) is (h(x)). Show that f(x) is
28. For each function in Exercise 1, determine whether that
(h(x)).
function is (x) and whether it is (x).
45. If f 1 (x) and f 2 (x) are functions from the set of positive
29. For each function in Exercise 2, determine whether that integers to the set of positive real numbers and f 1 (x) and
2
2
function is (x ) and whether it is (x ). f 2 (x) are both (g(x)),is (f 1 − f 2 )(x) also (g(x))?
30. Show that each of these pairs of functions are of the same Either prove that it is or give a counterexample.
order. 46. Show that if f 1 (x) and f 2 (x) are functions from the set
a) 3x + 7, x of positive integers to the set of real numbers and f 1 (x)
2
b) 2x + x − 7, x 2 is (g 1 (x)) and f 2 (x) is (g 2 (x)), then (f 1 f 2 )(x) is
((g 1 g 2 )(x)).
c) x + 1/2 , x
47. Find functions f and g from the set of positive integers
2
d) log(x + 1), log x
2 to the set of real numbers such that f (n) is not O(g(n))
e) log x, log x and g(n) is not O(f (n)).
10
2
31. Show that f(x) is (g(x)) if and only if f(x) is O(g(x)) 48. Express the relationship f(x) is (g(x)) using a picture.
and g(x) is O(f (x)). Show the graphs of the functions f(x) and Cg(x), as well
as the constant k on the real axis.
32. Show that if f(x) and g(x) are functions from the set
of real numbers to the set of real numbers, then f(x) is 49. Show that if f 1 (x) is (g 1 (x)), f 2 (x) is (g 2 (x)), and
O(g(x)) if and only if g(x) is (f (x)). f 2 (x) = 0 and g 2 (x) = 0 for all real numbers x> 0, then
(f 1 /f 2 )(x) is ((g 1 /g 2 )(x)).
33. Show that if f(x) and g(x) are functions from the set n n−1
of real numbers to the set of real numbers, then f(x) is 50. Show that if f(x) = a n x + a n−1 x + ··· + a 1 x +
(g(x)) if and only if there are positive constants k, C 1 , a 0 , where a 0 ,a 1 ,...,a n−1 , and a n are real numbers and
n
and C 2 such that C 1 |g(x)|≤|f(x)|≤ C 2 |g(x)| when- a n = 0, then f(x) is (x ).
ever x> k. Big-O, big-Theta, and big-Omega notation can be extended
to functions in more than one variable. For example, the state-
2
2
34. a) Show that 3x + x + 1is (3x ) by directly finding ment f (x, y) is O(g(x, y)) means that there exist constants C,
the constants k, C 1 , and C 2 in Exercise 33.
k 1 , and k 2 such that |f (x, y)|≤ C|g(x, y)| whenever x> k 1
b) Express the relationship in part (a) using a picture and y> k 2 .
2
2
showing the functions 3x + x + 1, C 1 · 3x , and 51. Define the statement f (x, y) is (g(x, y)).
2
C 2 · 3x , and the constant k on the x-axis, where 52. Define the statement f (x, y) is (g(x, y)).
C 1 ,C 2 , and k are the constants you found in part (a) 2 3 6 3
2
2
to show that 3x + x + 1is (3x ). 53. Show that (x + xy + x log y) is O(x y ).
4 4
5 3
3 3
3 5
54. Show that x y + x y + x y is (x y ).
35. Express the relationship f(x) is (g(x)) using a picture.
Show the graphs of the functions f(x), C 1 |g(x)|, and 55. Show that xy is O(xy).
C 2 |g(x)|, as well as the constant k on the x-axis. 56. Show that xy is (xy).
d
57. (Requires calculus) Show that if c> d > 0, then n is
36. Explain what it means for a function to be (1). c c d
O(n ),but n is not O(n ).
37. Explain what it means for a function to be (1).
58. (Requires calculus) Show that if b> 1 and c and d
c
d
38. Give a big-O estimate of the product of the first n odd are positive, then (log n) is O(n ),but n d is not
b
c
positive integers. O((log n) ).
b