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