Java Reference
In-Depth Information
3.13
Exercises
3.1 For each of the six expressions of Figure 3.1, give the range of values of n
for which that expression is most efficient.
3.2 Graph the following expressions. For each expression, state the range of
values of n for which that expression is the most efficient.
4n
2
log
3
n
3
n
n
2=3
20n
2
log
2
n
3.3 Arrange the following expressions by growth rate from slowest to fastest.
4n
2
log
3
n
3
n
n
2=3
n!
20n
2
log
2
n
See Stirling's approximation in Section 2.2 for help in classifying n!.
3.4 (a) Suppose that a particular algorithm has time complexity T(n) = 3
2
n
, and that executing an implementation of it on a particular machine
takes t seconds for n inputs. Now suppose that we are presented with a
machine that is 64 times as fast. How many inputs could we process on
the new machine in t seconds?
(b) Suppose that another algorithm has time complexity T(n) = n
2
, and
that executing an implementation of it on a particular machine takes
t seconds for n inputs. Now suppose that we are presented with a ma-
chine that is 64 times as fast. How many inputs could we process on
the new machine in t seconds?
(c) A third algorithm has time complexity T(n) = 8n. Executing an im-
plementation of it on a particular machine takes t seconds for n inputs.
Given a new machine that is 64 times as fast, how many inputs could
we process in t seconds?
3.5 Hardware vendor XYZ Corp. claims that their latest computer will run 100
times faster than that of their competitor, Prunes, Inc. If the Prunes, Inc.
computer can execute a program on input of size n in one hour, what size
input can XYZ's computer execute in one hour for each algorithm with the
following growth rate equations?
n
n
2
n
3
2
n
3.6 (a) Find a growth rate that squares the run time when we double the input
size. That is, if T(n) = X, then T(2n) = x
2
(b) Find a growth rate that cubes the run time when we double the input
size. That is, if T(n) = X, then T(2n) = x
3
3.7 Using the definition of big-Oh, show that 1 is in O(1) and that 1 is in O(n).
3.8 Using the definitions of big-Oh and , find the upper and lower bounds for
the following expressions.
Be sure to state appropriate values for c and n
0
.
