Java Reference
In-Depth Information
Complete Figure 5.10 with estimates for the running times that were
too long to simulate. Interpolate the running times for all four algo-
rithms and estimate the time required to compute the maximum con-
tiguous subsequence sum of 10,000,000 numbers. What assumptions
have you made?
5.17
The data in Figure 5.14 shows the result of running the maximum
subsequence sum problem in 1991. The program was written in the C
programming language and run on a Unix-based Sun 3/60 worksta-
tion with 4 Megabytes of main memory. This is the actual data from
that era.
a.
5.18
Verify that for each algorithm, the change in the observed running
time is consistent with the Big-Oh running time of the algorithm.
b.
Estimate the running time for
N
= 100,000 for the poorest performing
algorithm.
ON
( )
O
( )
c.
How much faster is the
algorithm compared to 1991?
d.
How much faster is the
algorithm compared to 1991?
e.
Explain why the answers for parts c and d are different. Is this
significant for two algorithms with different Big-Oh running
times? Is this significant for two algorithms with identical Big-Oh
running times?
Order the following functions by growth rate:
N
,
N
,
N
1.5
,
N
2
,
5.19
N
log
NN
,
log
log
N
,
NN
log
2
,
N
log
()
,
2
⁄
N
,
2
N
,
2
N
2
, 37,
2
/
N
3
, and
N
2
log
N
. Indicate which functions grow at the same rate.
figure 5.14
Figure 5.10 using
data from 1991.
N
O
N
( )
ON
( )
O
(
N
log
N
)
O
(
N
)
10
0.00193
0.00045
0.00066
0.00034
100
0.47015
0.0112
0.00486
0.00063
1,000
448.77
1.1233
0.05843
0.00333
10,000
NA
111.13
0.6831
0.03042
100,000
NA
NA
8.0113
0.29832
Search WWH ::
Custom Search