Due Date: Parts 1 and 2 are due Monday, June 25. Part 3
is due Thursday, June 28.
Objective: The goal of this assignment is to compare the
efficiency of different approaches to one specific problem:
search in a list of strings.
Assignment. Write the following three methods:
Our goal is to compare the speed of these methods. All three methods
run very fast (e.g., take less than a second of computation
time) for small values of the list size n, so it is not possible to
simply time the computations. However, we can estimate the time
accurately by using a system method that will return the current
system time in milliseconds as a long integer:
System.currentTimeMillis(). To estimate the time taken:
- First, assume that the list is given as an un-sorted array.
In this case, we need to use linear search to find an element
in this list.
- Second, assume that the list is given as a sorted array.
In this case, we can use binary search.
- Third, assume that the list is given as a linked list.
In this case, we also need to use linear search.
The difference between the two values is the
total number of milliseconds taken by your method. To get a more
accurate estimate you can run your method several times in a row and
compute the average time taken.
- call this method
before running your method and record the value;
- then run your
- when the method finishes running, call System.currentTimeMillis() again
to get the current time.
To test our methods, let us use a list consisting of squares
02=0, 12=1, 22=4, ..., (n
− 1)2, and let us search for a randomly
selected element in this list (use the Java random number
generator to select a random integer i from 0 to n − 1,
and search for the value i2). Run your program and
compare the times taken by the three methods for n = 1,000, n =
1,500, and n = 2,500. Record your observations and be able to
explain what is happening to your TA when you demo your