Outline

• runtime of programs
• algorithm efficiency
• Big-O notation
• linked lists
• nodes
• linked list implementation
• invariants

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

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.
• ArrayList add and remove methods

Linked list vs. array list

• in an array list, the elements of the list are stored in the array
• if more elements are needed, the array can be replaced with a bigger array
• that means the elements are stored in a single object (an array) whose size may be different depending on the number of elements
• instead, consider storing the elements into a variable number of objects
• where each object can only store one element
• so there will be as many container objects as there are elements in the list

Linked list

• each object that stores an element is called a Node
• the only difficulty with having a variable number of nodes is keeping track of them, that is, finding them when needed
• this is easy if each of the nodes holds a reference to another one of the nodes
• then, to keep track of all the nodes, we only need a reference to the first one
• following the reference in the first nodes, we get to the second nodes
• the reference in the second nodes refers to the third nodes
• meanwhile, each of the nodes also refers to one of the elements of the collection

     private class LinkedNode<T> {
       private T item;
       private LinkedNode<T> next;

       private LinkedNode(T value) {
         item = value;
         next = null;
       }

       private LinkedNode(T value, LinkedNode<T> reference) {
         item = value;
         next = reference;
       }
     }

Linked list nodes

• each node has two data fields: an element value, and a reference to the next node
  
• the element value has generic type T (or E -- it must match the type name in the class declaration)
• note that the reference to the next node is a pointer to the next node, and not the next node itself
• a private class is local to the enclosing (parent) class
• private data fields in the private class are accessible to the code in the parent class

Linked list implementation

• the linked list class only really needs one class variable: a reference to the start of the list, conventionally known as the head of the list
• the book also has a size class variable, which can be useful for error checking
• my implementation also keeps a reference to the last node in the linked list

Linked list performance

• in-class exercise: what is the run-time performance of add(E)?
• in-class exercise: what is the run-time performance of add(int, E)?
• in-class exercise: what is the run-time performance of remove(), which removes the head of the linked list?
• in-class exercise: what is the run-time performance of remove(int), which removes an arbitrary element?

Invariants

• There are some relations that must hold between the different class variables
• for example, size must always be the number of nodes in the linked list
• in a linked list of length 1, head == tail
• in a linked list of length 0, both head and tail should be null
• tail should be the node holding the last element of the list: a list traversal beginning at the head of the list should visit the tail node last of all
• these relations must always hold: they never change, that is, they are invariant (invariant is something that never changes)

Methods and Invariants

• every constructor must establish the invariants of the class
• every other method may expect that the invariants are true when the method is called, and
• every method must guarantee that the invariants are still true at the end of the method

Using Invariants

• invariants are useful for reasoning about the program
• some invariants can be checked by the program itself
• if an invariant is ever detected to not be true, the program should provide enough information to track down the bug (and should either crash, or re-establish the invariant)
• in ICS 211, if your classes have any invariants, your code should check them at the beginning and at the end of each public method
• this may help you improve your understanding of your code, and may also help you find bugs
• see also the linked list invariants
• if checking is slow, you may have to remove the invariant checking (e.g., add a return statement at the beginning of the check method) when doing performance testing