This HTML version of Think Data Structures is provided for convenience, but it is not the best format of the book. In particular, some of the symbols are not rendered correctly. You might prefer to read the PDF version. Or you can buy this book on Amazon.com. Chapter 2 Analysis of AlgorithmsAs we saw in the previous chapter, Java provides two
implementations of the 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:
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:
This kind of analysis lends itself to simple classification of algorithms. For example, if we know that the run time of Algorithm A tends to be proportional to the size of the input, n, and Algorithm B tends to be proportional to n^{2}, we expect A to be faster than B, at least for large values of n. Most simple algorithms fall into just a few categories.
2.1 Selection sortFor example, here’s an implementation of a simple algorithm called selection sort (see http://thinkdast.com/selectsort): public class SelectionSort { /** * Swaps the elements at indexes i and j. */ public static void swapElements(int[] array, int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } /** * Finds the index of the lowest value * starting from the index at start (inclusive) * and going to the end of the array. */ public static int indexLowest(int[] array, int start) { int lowIndex = start; for (int i = start; i < array.length; i++) { if (array[i] < array[lowIndex]) { lowIndex = i; } } return lowIndex; } /** * Sorts the elements (in place) using selection sort. */ public static void selectionSort(int[] array) { for (int i = 0; i < array.length; i++) { int j = indexLowest(array, i); swapElements(array, i, j); } } } The first method, The second method,
The third method, The first time
The sum of this series is n(n+1)/2, which is
proportional to n^{2}; and that means that To get to the same result a different way, we can think of
2.2 Big O notationAll constant time algorithms belong to a set called O(1). So another way to say that an algorithm is constant time is to say that it is in O(1). Similarly, all linear algorithms belong to O(n), and all quadratic algorithms belong to O(n^{2}). This way of classifying algorithms is called “big O notation”. NOTE: I am providing a casual definition of big O notation. For a more mathematical treatment, see http://thinkdast.com/bigo. This notation provides a convenient way to write general rules about how algorithms behave when we compose them. For example, if you perform a linear time algorithm followed by a constant algorithm, the total run time is linear. Using ∈ to mean “is a member of”: If f ∈ O(n) and g ∈ O(1), f+g ∈ O(n). If you perform two linear operations, the total is still linear: If f ∈ O(n) and g ∈ O(n), f+g ∈ O(n). In fact, if you perform a linear operation any number of times, k, the total is linear, as long as k is a constant that does not depend on n. If f ∈ O(n) and k is a constant, kf ∈ O(n). But if you perform a linear operation n times, the result is quadratic: If f ∈ O(n), nf ∈ O(n^{2}). In general, we only care about the largest exponent of n. So if the total number of operations is 2n + 1, it belongs to O(n). The leading constant, 2, and the additive term, 1, are not important for this kind of analysis. Similarly, n^{2} + 100n + 1000 is in O(n^{2}). Don’t be distracted by the big numbers! “Order of growth” is another name for the same idea. An order of growth is a set of algorithms whose run times are in the same big O category; for example, all linear algorithms belong to the same order of growth because their run times are in O(n). In this context, an “order” is a group, like the Order of the Knights of the Round Table, which is a group of knights, not a way of lining them up. So you can imagine the Order of Linear Algorithms as a set of brave, chivalrous, and particularly efficient algorithms. 2.3 Exercise 2The exercise for this chapter is to implement a In the code repository for this book (see Section 0.1), you’ll find the source files you’ll need:
You’ll also find the Ant build file When you run the tests, several of them should fail. If you examine the
source code, you’ll find four Before you start filling in the missing methods, let’s walk through some of the code. Here are the class definition, instance variables, and constructor. public class MyArrayList<E> implements List<E> { int size; // keeps track of the number of elements private E[] array; // stores the elements public MyArrayList() { array = (E[]) new Object[10]; size = 0; } } As the comments indicate, The constructor creates an array of 10 elements, which are initially
One detail about Java: you can’t instantiate an array using a type parameter; for example, the following will not work: array = new E[10]; To work around this limitation, you have to instantiate an array of
Next we’ll look at the method that adds elements to the list: public boolean add(E element) { if (size >= array.length) { // make a bigger array and copy over the elements E[] bigger = (E[]) new Object[array.length * 2]; System.arraycopy(array, 0, bigger, 0, array.length); array = bigger; } array[size] = element; size++; return true; } If there are no unused spaces in the array, we have to create a bigger
array and copy over the elements. Then we can store the element in the
array and increment It might not be obvious why this method returns a boolean, since it
seems like it always returns Finally, let’s look at public T get(int index) { if (index < 0  index >= size) { throw new IndexOutOfBoundsException(); } return array[index]; } Actually, In public T set(int index, T element) { // TODO: fill in this method. return null; } Read the documentation of HINT: Try to avoid repeating the indexchecking code. Your next mission is to fill in I’ve provided a helper method called
When you are done, run Only two more methods to go, and you’ll be done with this
exercise. The next one is an overloaded version of Again, read the documentation at http://thinkdast.com/listadd, write an implementation, and run the tests for confirmation. HINT: Avoid repeating the code that makes the array bigger. Last one: fill in the body of Once you have your implementation working, compare it to mine, which you can read at http://thinkdast.com/myarraylist. 
Are you using one of our books in a class?We'd like to know about it. Please consider filling out this short survey.
