Java Reference
In-Depth Information
where f(n)=n
2
.
Exercise R14.5. Suppose algorithm A takes 5 seconds to handle a data set
of 1,000 records. If the algorithm A is an O(n) algorithm, how long will it
take to handle a data set of 2,000 records? Of 10,000 records?
Exercise R14.6. Suppose an algorithm takes 5 seconds to handle a data set
of 1,000 records. Fill in the following table, which shows the approximate
growth of the execution times depending on the complexity of the
algorithm.
O(n)
O(n
2
) O(n
3
)
O(n
log(n)
O(2
n
)
1,000
5
5
5
5
5
2,000
3,000
45
10,000
For example, because 3,000
2
/l,000
2
=9, the algorithm would take 9 times
as long, or 45 seconds, to handle a data set of 3,000 records.
Exercise R14.7. Sort the following growth rates from slowest to fastest
growth.
O(n)
O(n log (n))
O(n
3
)
O(2
n
)
O(n
n
)
O( )
n
O(log(n))
O(n )
n
O(n
2
log(n))
O(n
log(n)
)
Exercise R14.8. What is the growth rate of the standard algorithm to find
the minimum value of an array? Of finding both the minimum and the
maximum?
660
661
Exercise R14.9. What is the growth rate of the following method?
public static int count(int[] a, int c)
{
int count = 0;
for (int i = 0; i < a.length; i ++)
