CSC152 2005S, Class 31: Algorithm Analysis Lab

Admin
* No work for Friday
* Don't forget the work for break!

Overview:
* Review
* Lab
* Reflection
* Other notes

About the lab:
* Read the algorithms and analyze them "theoretically"
* Read code to understand how I analyze them experimentally
* Run some experiments and "graph" the results
* Design your own experiments

Review:
* O(f(n)): Intented to model the running time of a method
  * Gives the shape of a curve that bounds the running time
  * Ignores constant multipliers  (c*f(n) is the same as f(n))
* Our goal: Figure out a good curve for each function
* To support that analysis: Experiments

What if our experimental results don't match our predicted running time?
* Our analysis is wrong
* The language does not work the way we expect
  * Something we expect to be "constant time" isn't
* Other factors are involved (e.g., some game is running, too)
* Our implementation might not match the actual algorithm
* Our analysis is worst case, most experiments are average case

Do the lab with a partner!
* East meets West

Why is it a constant multiplier?
* We say that it's "constant" if it doesn't depend on n (or x)
* Because "wall clock" time (System.currentTimeMillis()) may
  vary from computer to computer, particularly as individual
  operations vary in time, we really care only about the shape
  of the curve (at least at this point in the analysis)

Why do I get the stupid error message?
* Because Sam has not yet adapted to the new version of Java

WARNING!  Before you test sequentialSearch, reload the lab
and make a copy of NewComputer.java.  You should probably
build an array of Integer objects.