CSC152 2006S, Class 35: Algorithm Analysis (3): Experiments

Admin:
* Readings and homework for Friday tbd.
* EC for cool scientific visualization talk today at 4:30.
* So, what did you learn yesterday (in this class)?

Overview:
* Review
* Lab

/Review/

* Big O notation is mathematical
* But we don't have to pay attention to most of the math
* We can analyze algorithms as engineer, mathematician, and scientist
* Exponentation can be done efficiently if you have ln and e^x tables
* Big O notation lets us ignore constant multipliers and smaller-order terms

* What does smaller order mean?
  x^m is smaller order than x^n if m < n?
  logx is smaller order than x
  constant is smaller order than logx
  smaller order is transitive
  if f(x) is smaller order than g(x) then h(x)*f(x) is smaller order than h(x)*g(x), e.g., since 1 is smaller order than log(x), x is smaller order than xlogx

In BigO, we say O(n), not O(n + logn + 1)

In practice:  Don't worry about the formal def'n: Worry about the overall shape
* Count!
  * Basic operations
  * Worst of the cases in an if
  * Body of loop * number of repetitions
  * Steps in function call