s
Section 5.5 Order of Magnitude
421
Case 1: a < b
c
. From a < b
c
we get (taking log b of both sides)
log b a < c or w < c
In the right side of Equation (7), n
c
is the highest-power term and has a positive
coefficient (because b
c
− a > 0). Therefore S(n) = Θ(n
c
).
Case 3: a > b
c
. From a > b
c
we get (taking log b of both sides)
log b a > c or w > c
In the right side of Equation (7), n
w
is the highest-power term and has a positive
coefficient (because a − b
c
> 0). Therefore S(n) = Θ(n
w
) = Θ(n
log b a
).
Case 2: a = b
c
. This is an easy case to prove and is left for you to do (see
Exercise 28).
S e c t I o n 5 . 5 Review
technIQueS
• Determine whether two functions are the same
order of magnitude.
• Use the master theorem to find an order-ofmagnitude expression for the solution to certain
divide-and-conquer recurrence relations.
maIn IDeaS
• Functions can be grouped into equivalence classes
according to their order of magnitude, which is a
measure of their growth rate.
• Big theta, big oh and little oh (Θ, O, o) are
notations for relating the growth rates of two
functions.
exeRcISeS 5.5
1. Prove, by finding constants that satisfy the definition of order of magnitude, that f = Θ(g) if f (x) = x and
g(x) = 17x + 1.
2. Prove, by finding constants that satisfy the definition of order of magnitude, that f = Θ(g) if
f (x) = 3x
3
− 7x and g(x) = x
3
∙2.
3. Prove, by finding constants that satisfy the definition of order of magnitude, that f = Θ(g) if
f (x) = 29x
2
− 4x − 15 and g(x) = 15x
2
+ x.
4. Prove, by finding constants that satisfy the definition of order of magnitude, that f = Θ(g) if
f (x) = !x + 100 and g(x) = "x.
5. Prove, by finding constants that satisfy the definition of order of magnitude, that f = Θ(g) if
f (x) = x
3
+ log x and g(x) = x
3
.
6. Prove, by finding constants that satisfy the definition of order of magnitude, that f = Θ(g) if
f (x) = log(3x
2
) and g(x) = log x.
7. In this section, we noted that h 1 = Θ(h) implies that from some point on, h 1 is within an “envelope” of h.
Can this envelope ever be entirely above or entirely below h? Explain.
8. Prove that if f 1 , is a function that is Θ(g 1 ) and f 2 is a function that is Θ(g 2 ), then the function f 1 + f 2 ,
defined by ( f 1 + f 2 )(x) = f 1 (x) + f 2 (x), is Θ(max(g 1 , g 2 )), where (max(g 1 , g 2 ))(x) = max(g 1 (x), g 2 (x)).
9. Find the smallest integer n for which x log x is O(x
n
).
10. Find the smallest integer n for which (x
4
+ 4x)∙(x + 2) is O(x
n
).
W