Due Date: Monday, February 21 or
Tuesday, February 22,
depending on the day of your lab.
Objective: The goal of this assignment is to compare the
efficiency of different approaches to one specific problem:
search in a list.
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 elements 0, 1, 2,
3, ..., n - 1, n, and let us search for a randomly selected
element in this list (use random number generator to select the
element). Run your program and compare the times taken
by the three methods for n = 500, n = 1,000, and
n = 2,000. Record your observations and be able to explain what is
happening to your TA when you demo your program.