Page 239 - Discrete Mathematics and Its Applications

218 3 / Algorithms

59. (Requires calculus) Show that if d is positive and b> 1, 69. (Requires calculus) Show that if f 1 (x) is O(g(x)) and
d
d
n
n
then n is O(b ) but b is not O(n ). f 2 (x) is o(g(x)), then f 1 (x) + f 2 (x) is O(g(x)).
n
60. (Requires calculus) Show that if c> b> 1, then b is 70. (Requires calculus) Let H n be the nth harmonic number
n
n
n
O(c ) but c is not O(b ).
The following problems deal with another type of asymptotic 1 1 1
notation, called little-o notation. Because little-o notation is H n = 1 + 2 + 3 + ··· + n .
based on the concept of limits, a knowledge of calculus is
needed for these problems. We say that f(x) is o(g(x)) [read Show that H n is O(log n).[Hint: First establish the in-
f(x) is “little-oh” of g(x)], when
equality
f(x)
lim = 0. n n
x→∞ g(x) 1 1
< dx
j 1 x
61. (Requires calculus) Show that j=2
2
3
2
a) x is o(x ). b) x log x is o(x ).
2
2
2
x
c) x is o(2 ). d) x + x + 1isnot o(x ). by showing that the sum of the areas of the rectangles of
62. (Requires calculus) height 1/j with base from j − 1to j, for j = 2, 3,...,n,
is less than the area under the curve y = 1/x from 2 to n.]
a) Show that if f(x) and g(x) are functions such that
f(x) is o(g(x)) and c is a constant, then cf (x) is ∗ 71. Show that n log n is O(log n!).
o(g(x)), where (cf )(x) = cf (x). 72. Determine whether log n! is (n log n). Justify your an-
b) Show that if f 1 (x), f 2 (x), and g(x) are functions swer.
such that f 1 (x) is o(g(x)) and f 2 (x) is o(g(x)),
∗ 73. Show that log n! is greater than (n log n)/4 for
then (f 1 + f 2 )(x) is o(g(x)), where (f 1 + f 2 )(x) =
f 1 (x) + f 2 (x). n> 4. [Hint: Begin with the inequality n! >
n(n − 1)(n − 2) ···Ðn/2 .]
63. (Requires calculus) Represent pictorially that x log x is
2
2
2
o(x ) by graphing x log x, x , and x log x/x . Explain Let f(x) and g(x) be functions from the set of real num-
2
how this picture shows that x log x is o(x ). bers to the set of real numbers. We say that the func-
tions f and g are asymptotic and write f(x) ∼ g(x)
64. (Requires calculus) Express the relationship f(x) is if lim x→∞ f (x)/g(x) = 1.
o(g(x)) using a picture. Show the graphs of f(x), g(x),
and f (x)/g(x). 74. (Requires calculus) For each of these pairs of functions,
∗ 65. (Requires calculus) Suppose that f(x) is o(g(x)). Does determine whether f and g are asymptotic.
2
2
it follow that 2 f(x) is o(2 g(x) )? a) f(x) = x + 3x + 7, g(x) = x + 10
2
∗ 66. (Requires calculus) Suppose that f(x) is o(g(x)). Does b) f(x) = x log x, g(x) = x 3
8
4
it follow that log |f(x)| is o(log |g(x)|)? c) f(x) = x + log(3x + 7),
2
67. (Requirescalculus)Thetwopartsofthisexercisedescribe g(x) = (x + 17x + 3) 2
4
2
3
the relationship between little-o and big-O notation. d) f(x) = (x + x + x + 1) ,
3
2
3
4
a) Show that if f(x) and g(x) are functions such that g(x) = (x + x + x + x + 1) .
f(x) is o(g(x)), then f(x) is O(g(x)). 75. (Requires calculus) For each of these pairs of functions,
b) Show that if f(x) and g(x) are functions such that determine whether f and g are asymptotic.
f(x) is O(g(x)), then it does not necessarily follow a) f(x) = log(x + 1), g(x) = log x
2
that f(x) is o(g(x)). x+3 x+7
b) f(x) = 2 , g(x) = 2
68. (Requires calculus) Show that if f(x) is a polynomial of 2 x x 2
degree n and g(x) is a polynomial of degree m where c) f(x) = 2 , g(x) = 2 2
2
m>n, then f(x) is o(g(x)). d) f(x) = 2 x +x+1 , g(x) = 2 x +2x
3.3 Complexity of Algorithms
Introduction
When does an algorithm provide a satisfactory solution to a problem? First, it must always
produce the correct answer. How this can be demonstrated will be discussed in Chapter 5.
Second, it should be efficient. The efficiency of algorithms will be discussed in this section.
How can the efficiency of an algorithm be analyzed? One measure of efficiency is the time
used by a computer to solve a problem using the algorithm, when input values are of a specified