Review of runtimes (Big O)
draft1: 11/7/2006, dis
draft2: 11/12/2006: Nikos K adds pivot info on q-sort

Search:
+ best case: 
  lucky guess: O(1)

+ linear search array: O(n)
  need to check each element one at a time

+ binary search array: O(log n) 

  * n ~ 2^k
 
  * number of guesses (k) found by dividing search space (n)
    in half over and over again -- so, total amount of search time
    grows slowly (divide search space in half each time)
 
  * downside: need to sort array, which is O(nlogn)

  * upside: you might need to sort only once

Sorting:
http://cg.scs.carleton.ca/~morin/misc/sortalg/

- Selection sort: 
  * best, average, worst: O(n^2)
  (why?)

- Insert sort:
  * best: O(n)
  (why?)
  * average, worst: O(n^2)
  (why?)

- Merge sort:
  * best, average, worst: O(nlogn)
  (why?)

- Quick sort:
  * average, best: O(nlogn)
  (why?)
  * worst: O(n^2)
  (why?)

  * pivot: If one can find the median element in O(n) then the worst
    case complexity is the same as mergesort since the two recursive calls 
    deal with arrays of equal size.

    How to find the median in O(n) worst case time? The idea is that we
    partition the array in n/5 sets of 5 elements, compute the medians of 
    these sets and then compute the median of these medians (recursively).
    We then partition the array around this median of medians and 
    recursively continue working on the correct partition (on that 
    partition however we are not trying to find the median but the k-th 
    element where k can be easily computed from n/2 and the sizes of the 
    left and right partitions)

    A better description and the complexity analysis can be found here
    http://www.ics.uci.edu/~eppstein/161/960130.html

    So quicksort can be made to run in O(nlogn) worst case time but in 
    practice everyone uses some easier to implement rule for selecting the 
    pivot.

1-D Arrays:

- extract element: O(1)
  can index directly into array

- find element: O(n) or O(log n)
  see Search

- add element:
  
  * if inserting into current array, O(1)
    (direct access)
 
  * if need to expand array, you should double the size of the
    array (why? short answer: assume you start with 1 element and 
    increase your need by 1; add how much wasted space space you
    get if you do and don't double): O(n^2) for no doubling, O(n) for doubling

    http://everything2.com/index.pl?node_id=764980

- delete element: O(1) (direct access)

- why not just use arrays for everything if they're so great?

  * difficulty in growth (added space, O(n))
  * wasted space: old languages didn't have dynamic allocation
    which meant you needed to set an initial array limit!
  
Lists:

- a lot depends on implementation: 
  * head pointer
  * head and tail pointer
  * tail pointer
  * etc...

- insert: O(1) 
  likely you're using a head pointer and you put the new element at the head
  (could also do tail)

- inserting in a specific location: O(n)
  it's like searching the list, counting along the way -- you could feasibly
  count everything (like linear search)

- get: O(1)
  if you stick everything at the end and have only a tail pointer, you just
  cost yourself O(n)

- search: O(n)
  sorting a list could be painful, though you could do it (so, O(nlogn))
  
- get from a specific location: see inserting at a location

- sorted lists:
  ?

Dictionaries:

- think "key-value"
 
- Operations:
  void insert (Object key, Object value);
  void update (Object key, Object value);
  Object find (Object key);
  void remove (Object key);
  boolean isEmpty ( );
  void makeEmpty ( );


- array runtimes:

         unsorted  sorted
  insert O(1)      O(n)
  update O(n)      O(log n)
  find   O(n)      O(log n)
  remove O(n)      O(n)

  insert could be O(n) (worst case and rarely)

- list runtimes:

  * sorted and unsorted doesn't matter
  * insert, remove, traverse all O(n)

- hashtables:

  * O(1) expected time
  * runtimes tend to be expected, not worst case

- BSTs:

  * balanced tree: O(h) (height of tree)
  * unbalanced: O(n) (# of items)
  * so, worst-case time is O(logn) whereas
    hashtable is expected time of O(1)
    (hashtable worst case is O(n))
  * can do other ops with BST

Stacks:

- linked (Vector, List, ...):
  
  * make head point to top of stack
  * get O(1)

- array:

  * will likely waste space
  * O(1) except if you need to add more space (O(n))

Queues:

- linked:

  * use head and tail refs
  * O(1)

- array:

  * use circular array
  * O(1) except if need to grow array (O(n))

Heaps:

  * getMax: 
    skinny tree: O(n) (list)
    fat tree: O(logn)

  * build heap: 
    build from bottom up using bubble down, O(n)

  * Heap sort: 
    use heap as array: getMin: O(nlogn)

Priority Queues:

  
             Unordered  Ordered  Unordered  Ordered  BST        Balanced
                List     List      Array     Array                 BST
  insert       O(1)       O(n)      O(1)      O(n)   O(logn)     O(logn)
                                                     (expected)  (worst-case)

  removeMax    O(n)       O(1)      O(n)      O(1)   O(logn)     O(logn)
                                                     (expected)  (worst-case)

Binary Search Trees:

- height of full or complete tree: logn (or, log[2]n+1 rounded up)

- search: 

  * skinny: O(h) (O(n) if tree is "listy")
  * full/complete: O(logn)

- see algorithms for balancing a BST

Others:

- sets
- graphs
- BFS, DFS