Outline

• List interface
• Array lists
• runtime of programs
• algorithm efficiency
• Big-O notation

Lists

• From the book (p. 62/193):

  A list is an expandable collection of elements in which each element has a position or index.

• there are many lists, usually categorized by how they are implemented:
  • ArrayLists are implemented using arrays (Vectors are similar)
  • LinkedLists are implemented using links (references) to objects
• All lists are derived from the abstract class AbstractList, and implement the List interface (even AbstractList implements the List interface)
• unlike arrays, lists can grow and shrink
• most lists can also insert elements in-between existing elements, and likewise remove elements without leaving a gap
• lists also have operations to search for elements, and do something with every element of the list

Generic interface

• a list can store object of any one type:
  • a list of strings: List<String>
  • a list of integers: List<Integer>
  • a list of objects: List<Object>
• the notation "List<E>" indicates that the list interface is parametrized over the type E of objects it can store
• in this case, E is a type parameter
• classes can use the same notation
• these are called generic interfaces or classes
• collection classes, which can store objects of any type, are often generic
• the Java compiler can check that the type parameter is the same for every use of a variable: for example, that all operations involving a List<String> actually store and retrieve strings

List Interface

public interface list<E> extends Collection<E> {
    E get(int index);       // returns object at given position
    E set(int index, E element);  // sets object, returns old value
    int indexOf(Object o);  // returns index of object in list
    E remove(int index);    // removes object at the given position
    int size();             // returns number of elements in list
    boolean add(E element); // add element at the end of the list
    void add(int index, E element); // add element at given position 
    ...
}

• AbstractList<E> essentially provides the same methods as List<E>
• the methods implemented by AbstractList provide very basic functionality for immutable lists

ArrayList<E> Class

• an array list uses an array to store the objects in the list
• the object at position i in the list are found at array index i
• when the array needs to grow, a bigger array is allocated, and data is copied from the old array to the new array
• this is an expensive operation: it takes time proportional to the total size of the collection
• in general, the underlying array may have more elements than the collection (since the collection does not have to store a value on every element of the array)
• so an array list always has a capacity that is greater than or equal to its size

ArrayList<E> implementation

• must have an actual array of objects of type E
• must keep track of the size
• the capacity is the same as the array length

public class ArrayList<E> {
   protected E [] data;
   protected int size;

   @SuppressWarnings("unchecked")
   public ArrayList() {
     data = (E []) new Object [16];
   }

• Java will not allocate an array with a type that is not know at compile time
• @SuppressWarnings("unchecked") is used to suppress warnings about the type conversion not being checked

Adding at the end of an ArrayList<E>

• if there is room, adding at the end is easy:

   public boolean add(E value) {
     data [size] = value;
     size++;
     return true;
   }

• if there is no room, we will need to make room by reallocating the array:

   public boolean add(E value) {
     if (size == data.length) {
       data = Arrays.copyOf(data, data.length * 2);
     }
     data [size] = value;
     size++;
     return true;
   }

• In-class exercise: (with a friend), implement this method to add a value somewhere in the middle of the array. Assume that the index is valid, i.e. index >= 0 and index < data.length.
• Your code must shift all the data that is at or after index, so there is room for one new element

   public void add(int index, E value) {

Runtime of programs

• compare the following two program fragments:

  int result = 1;                       int result = 1;
  for (int i = 2; i <= n; i++) {          for (int i = n; i > 0; i--) {
    result = result * i;                    result = result * i;
  }                                       }
  

• how many multiplications does each of these fragments perform?
• how many additions or subtractions does each of these fragments perform?
• how many comparisons does each of these fragments perform?
• are there any other differences between the two, and if so, how many times are they performed?

program runtime analysis

• for a small-sized problem, runtime is generally small
• runtime may matter for large-sized problems
• runtime may matter if the time of individual operations is long
• for example:
  • arithmetic by hand takes much longer than arithmetic by computer, by a factor of 10⁹ or so
  • so a billion sums by a computer may be faster than 1 sum by a human
  • the same is true, to some extent, about comparisons among computers
• to compare algorithms, we need a method that is independent of the specific computing hardware
• the operations that matter most are the ones that are repeated, especially when the number of repetitions depends on the size of the problem
• what is the size of the fact problem above?

big O notation

• big O notation is a way of indicating how fast an algorithm's runtime increases with increases in problem size
• for example, the algorithm to compute fact takes time O(n), whether implemented recursively or iteratively. Here, n is the input to the algorithm and also the "size" of the problem
• O(n) is the worst-case running time for this problem
• searching through a list of n items in sequence is also O(n). Here, n is the size of the problem but not the input to the problem
• big O can be defined mathematically: given suitable constants k and n₀, an algorithm A(n) being O(f(n)) means for n > n₀ the runtime of A(n) <= k * f(n)

common functions used with big O

• common f(n) include:
  • O(1) or constant time
  • O(log n) or logarithmic time:
    since log₂ n = k₁ * ln n = k₂ * log₁₀ n, any logarithm will do
  • O(n) or linear time
  • O(n log n), where a (worst-case) logarithmic operation is repeated at most n times
  • O(n²) or quadratic time
  • O(n³) or cubic
  • O(2ⁿ) or exponential
• in-class exercise (everyone together): what is the value of f(n) for each of these when n = 10? when n = 100?
• searching through a list of n items in sorted order (e.g. in a phone book) can be O(log n)
• finding all pairs of matching items in an unsorted list of n items can be O(n²)

big O examples

• doing a fixed number of things is O(1)
• dividing something in two nearly equal parts can only be done O(log n) times
• going through every element of an input (or even every third element) is O(n), linear
• comparing every element of an input to every other element is O(n²), quadratic
• trying every combination of n inputs is O(2ⁿ), exponential

big O growth

• O(1) means: doubling n -- run time is unchanged. For example, array access time is independent of array size
• O(log n) means: doubling n -- the run time increases by a constant factor
• O(n) means: doubling n -- the run time doubles. For example, looking at every element of an array takes time proportional to the array size
• O(n log n) grows faster than O(n), but not as fast as O(n²)
• O(n²) means: doubling n -- the run time increases by a factor of four
• O(2ⁿ) means: increasing n by just 1 -- the run time doubles (or is multiplied by any fixed factor)

figuring out big O

• suppose the number of operations required for an algorithm is 2ⁿ + n³ + n log n + 13
• the 2ⁿ term will grow the fastest: k * n³ < 2ⁿ for sufficiently large n, no matter how large k is
• so the slower-growing terms can be ignored and this algorithm is O(2ⁿ)
• constants can likewise be ignored: O(1) = O(5) = O(17), usually written as O(1). Similarly, O(n/3) = O(n)
• the problem size can be expressed as a combination of numbers, for example the time to search a room (of size m by n) is proportional to m * n, and any algorithm to do so is likely to be O(m * n)
• big O always reflects the worst case

In-class exercise: big O for

• Assignment 1
• Loops.java, which produced this output.