CSC 152 2005F, Class 34: Algorithm Analysis (2) Admin: * Walker observes * About CSC295 * Homework: Lab on Algorithm Analysis Overview * Review * Big-O Notation * Eliminating constants * Using the notation: Relating functions * Analyzing recursive methods About the HW * Counting by hand is annoying * Prediction for "slow" version: If we double the size, we should multiply the time by 4 * Prediction didn't necessarily match. Why? * Counting by hand is approximate * Doesn't account for time to create vector * We're modeling, and models don't always work * Our prediction could have been wrong Review: * We're analyzing the running speed of algorithms * We can approximate the running speed of algorithms by "counting" steps statically * We can also try experiments * Constants give us headaches A formal approach * Can we come up with a mathematical notation that helps us model the running time? * And helps us ignore the stuff we don't care about * We care about *an upperbound* on *the shape of the curve* when *input is large enough* * Plus get rid of those annoying constants * Notation: Big-O O(f(n)) is a "set" of all functions bounded above by f(n) (ignoring constant multiplers) g(n) is in O(f(n)) iff exists d, n0 s.t. for all n > n0 |g(n)| <= |d*f(n)| Prove that g(n) = 2n^2 is O(n^2) Let n0 be 1 Let d be 3 2n^2 vs. 3*n^2: 2n^2 < 3n^2 Consider g(n) = 100n vs f(n) = n^2 For n = 5, g(n) = 500, f(n) = 25 For n = 10, g(n) = 1000, f(n) = 100 Let n0 = 100 Let d = 1 g(n) = 100*n f(n) = n*n > n*100, so f(n) > g(n) Consider f(n) = 100n vs g(n) = n^2 If g(n) in O(f(n))? Look at the shape. It's in O(???) If f(n) is in O(h(n)) and g(n) is in O(h(n)) What do we know about f(n)+g(n)? Bounded above by h(n) ; in O(h(n)) If f(n) is in O(g(n)) and g(n) is in O(h(n)) f(n) is in O(h(n)) f(n) + g(n) is in O(g(n)) We get to throw away lower-order terms when using Big-O analysis running time is c*n^2 + d*n + e * BigO basics say "throw away constants" n^2 + n + 1 "The running time is in O(n^2 + n + 1)" n^2 + n + 1 is in O(n^2) because n is in O(n^2) and 1 is in O(n^2) What about analyzing recursive functions? (define sum (lambda (x) (if (null? x) // 1 0 // 1 (+ // 1 (car x)// 1 (sum // The running time of sum. Whoops. (cdr x)))))) // 1 * Hand waving. We look at each element once. We do a constant amount of work for each element. Hence, it's in O(n) * Code rewrite. Rephrase the recursive as iteration and use normal counting * Recurrence analysis t(n) = "the amount of time sum takes on an input of size n" t(0) = c t(n) = d + t(n-1) // Technique: Repeatedly expand right-hand-side and look for // patterns t(n) = d + d + t(n-2) = 2d + t(n-2) t(n) = 2d + d + t(n-3) = 3d + t(n-3) t(n) = 3d + d + t(n-4) = 4d + t(n-4) t(n) = kd + t(n-k) When n-k = 0, k = n t(n) = n*d + t(0) = n*d + c in O(n)