Java Reference
In-Depth Information
3.24 Prove that if an algorithm is (f(n)) in the average case, then it is O(f(n))
in the best case.
3.14
Projects
3.1 Imagine that you are trying to store 32 Boolean values, and must access
them frequently. Compare the time required to access Boolean values stored
alternatively as a single bit field, a character, a short integer, or a long integer.
There are two things to be careful of when writing your program. First, be
sure that your program does enough variable accesses to make meaningful
measurements. A single access takes much less time than a single unit of
measurement (typically milliseconds) for all four methods. Second, be sure
that your program spends as much time as possible doing variable accesses
rather than other things such as calling timing functions or incrementing
for
loop counters.
3.2 Implement sequential search and binary search algorithms on your computer.
Run timings for each algorithm on arrays of size n = 10
i
for i ranging from
1 to as large a value as your computer's memory and compiler will allow. For
both algorithms, store the values 0 through n 1 in order in the array, and
use a variety of random search values in the range 0 to n 1 on each size
n. Graph the resulting times. When is sequential search faster than binary
search for a sorted array?
3.3 Implement a program that runs and gives timings for the two Fibonacci se-
quence functions provided in Exercise 2.11. Graph the resulting running
times for as many values of n as your computer can handle.
