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