TIMING THE ARRAYLIST AND LINKEDLIST CLASSES

In this lab, you will create a couple of tasks whose times clearly distinguish between the ArrayList and LinkedList classes.

Analyzing Run Times for ArrayList and LinkedList

In Chapters 6 and 7, we discussed when an ArrayList would be faster than a LinkedList: any task in which random access was critical. We also considered when a LinkedList would be faster than an ArrayList: for inserting or deleting elements far from the last element in the list.

Suppose we have created an ArrayList or LinkedList of n elements, where the value for n is input by the end-user. Here is a specific example of the first scenario:

task1: for each of n indexes, randomly generated, retrieve the list element at that index.

For an ArrayList, it takes only constant time -- on average -- to generate one random index and only constant time -- on average -- to retrieve the element at that index. In task1, there are n index generations and n element retrievals, so task1's averageTime (n) is linear in n when an ArrayList is used.

For a LinkedList, it takes only constant time -- on average -- to generate one random index, but it takes time linear in n -- on average -- to retrieve the element at that index. In task1, there are n index generations and n element retrievals, so task1's averageTime (n) is quadratic in n when a LinkedList is used.

Run-time estimates can vary widely from one computer system to another, and even from one run to the next on a given computer system. In practice, we will not attempt to compute the run time for a given task of size n, but we will crudely estimate its value from elapsedTime (n). For example, if averageTime (n) is linear in n, then

elapsedTime (2n) ~ K (2n)

                 = 2 K n

                 ~ 2 elapsedTime (n)

So if elapsedTime (10000) ~ 1.0 seconds, then elapsedTime (20000) ~ 2 elapsedTime (10000) ~ 2.0 seconds. Similarly, elapsedTime (50000) ~ 5.0 seconds. The closeness of these approximations depends on a variety of factors, such as whether the computer system is multitasked and the size of the disk cache.

For tasks whose averageTime (n) is quadratic in n, the analysis is slightly more complicated. If averageTime (n) is quadratic in n, then elapsedTime (n) ~ K n² seconds, for some positive constant K. So, for example, we can estimate the time when we triple n as follows:

elapsedTime (3n) ~ K ((3n)²)

                 = 9K (n²)

                 ~ 9 elapsedTime (n)

So if a quadratic-time method takes about 5 seconds for 10000 items, then the same method will take about 45 seconds for 30000 items. That is, when the number of items increases by a factor of three (from 10,000 to 30,000), the elapsed time increases by approximately a factor of 3 squared, that is, 9.

As noted in Chapter 3, these estimates should not be taken too seriously.