Think Data Structures

Chapter 2. Analysis of Algorithms

As we saw in the previous chapter, Java provides two implementations of the List interface, ArrayList and LinkedList. For some applications LinkedList is faster; for other applications ArrayList is faster.

To decide which one is better for a particular application, one approach is to try them both and see how long they take. This approach, which is called profiling, has a few problems:

1. Before you can compare the algorithms, you have to implement them both.

2. The results might depend on what kind of computer you use. One algorithm might be better on one machine; the other might be better on a different machine.

3. The results might depend on the size of the problem or the data provided as input.

We can address some of these problems using analysis of algorithms. When it works, algorithm analysis makes it possible to compare algorithms without having to implement them. But we have to make some assumptions:

1. To avoid dealing with the details of computer hardware, we usually identify the basic operations that make up an algorithm—like addition, multiplication, and comparison of numbers—and count the number of operations each algorithm requires.

2. To avoid dealing with the details of the input data, the best option is to analyze the average performance for the inputs we expect. If that’s not possible, a common alternative is to analyze the worst case scenario.

3. Finally, we have to deal with the possibility that one algorithm works best for small problems and ...