Java Reference
In-Depth Information
In terms of N , what is the running time of the following algorithm to
compute
5.11
X N
:
public static double power( double x, int n )
{
double result = 1.0;
for( int i = 0; i < n; i++ )
result *= x;
return result;
}
Directly evaluate the triple summation that precedes Theorem 5.1.
Verify that the answers are identical.
5.12
For the quadratic algorithm for the maximum contiguous subse-
quence sum problem, determine precisely how many times the inner-
most statement is executed.
5.13
An algorithm takes 0.5 ms for input size 100. How long will it take
for input size 500 (assuming that low-order terms are negligible) if
the running time is
a.
5.14
linear
b.
c.
O ( N log N )
quadratic
d.
cubic
An algorithm takes 0.5 ms for input size 100. How large a problem
can be solved in 1 minute (assuming that low-order terms are negligi-
ble) if the running time is
a.
5.15
linear
b.
c.
O ( N log N )
quadratic
d.
cubic
For 1,000 items, our algorithm takes 10 sec. to run on machine A, but
now you replace the machine with machine B that is 2 times as fast.
Approximately how long will the algorithm take to run on machine B
for 2,000 items if the algorithm is:
a.
5.16
linear
b.
quadratic
c.
d.
ON ( )
O ( N log N )
Search WWH ::




Custom Search