422
Relations, Functions, and Matrices
Exercises 11–18 require familiarity with ideas from calculus. As an alternative to the definition of order of
magnitude, a limit test can be used to prove that f = Θ(g):
f = Θ(g) if lim
xS ∞
f (x)
g (x)
= p
where p is a positive real number
As an aid in finding the limit of a quotient, if lim xS ∞ f (x) = ∞ and lim xS ∞ g(x) = ∞ and f and g are
differentiable functions, then L’Hôpital’s rule says that
lim
xS ∞
f (x)
g(x)
= lim
xS ∞
f ′(x)
g′(x)
Thus 2x
2
+ 7 = Θ(x
2
) because
lim
xS ∞
2x
2
+ 7
x
2
= lim
xS ∞
4x
2x
= 2
11. Use the limit test to do Exercise 1 again.
12. Use the limit test to do Exercise 2 again.
As another limit test, if
lim
xS ∞
f(x)
g(x)
= 0
then f = o(g).
13. Use the second limit test to prove that x = o(x
2
).
14. Use the second limit test to prove that "x = o(x).
15. Use the second limit test to prove that log x = o(x).
16. Use the second limit test to prove that (ln x)
2
= o(x
0. 5
) where ln x is the natural log of x, log e x.
17. Use both limit tests to group the following functions into classes by order of magnitude and to order those
classes. Here ln x is the natural log of x, log e x.
17 x log x, 200 log x, 2
x
− x
2
, "
4
x, 10x
2
− 3x + 5, 420x, 41 ln x
2
18. Use both limit tests to group the following functions into classes by order of magnitude and to order those
classes. Here ln x is the natural log of x, log e x.
x, "x, log x, x
3
, x log x, 2x
3
+ x, e
x
, (log x)
2
, ln x, x
3
+ log x
19. You ask three different people to give you a worst-case order-of-magnitude expression for the work done
by a particular algorithm on an input of size n. You receive three answers:
i. O(n
3
)
ii. o(n
3
)
iii. Θ(n
2
)
Which is the most useful and why?