CSC152 2005F, Class 35: Algorithm Analysis (3) Overview: * Sorry about problem in lab. * Eryn wants to know why you don't visit her. * Homework to be determined. Admin: * Review * Detour: Counting deletions * Lab discussion * Recurrence relations Review: * Focusing on analyzing the running time of algorithms * Big O analysis * Puzzling mathematical notation * The notation lets us ignore things (say that the "don't matter") * Constant multipliers: n^2 vs. n matters more than 2n vs 3n n^2 will dominate d*n no matter what d we choose * Lower order terms: n^2 plus something smaller than n^2 is not much different than n^2 for big enough n * If two methods are both O(n^2), big O analysis does not provide a good technique for deciding which is faster. * Experiments will help * Big O notation: See real whiteboard (no photos available) * Use this to prove the things we expect/want * Return to the notation in CSC301 Detour: Counting deletions int len = stuff.size(); // O(1) for (int i = 0; i < len; i++) { // O(len) or O(n) repetitions stuff.remove(0); // O(n) } O(n) repetitions of an O(n) step is O(n^2) Does it make a difference that we've said remove is O(n) when, for many values, it's constant. * We're bounding above, not bounding exactly, so it's okay. * In real life (or at least computer life) is strive for a "close" upper bound * Let's do the more careful analysis, only in terms of deletion N + (N-1) + (N-2) + (N-3) + .... + 5 + 4 + 2 + 1 That sum has the value N(N+1)/2 is O(N^2) Lab For exptFor(x,n), what is the running time in terms of n? + O(n^2) + O(n) **** BigDecimal result = new BigDecimal(1.0); for (int i = 0; i < n ; i++) { // N repetitions this.step(); result = result.multiply(x); // c steps } return result; For exptWhile(x,n), what is the running time in terms of n? public BigDecimal exptWhile(BigDecimal x, int n) { BigDecimal accumulator = new BigDecimal(1); // need to repeatedly reduce the power. Idea: // currentx^currentn * accumulator = originalx^originaln while (n > 0) { this.step(); // If n is even, divide it by two and multiply x by // itself, using the amazing rule that // (x^n = (x^2)^(n/2)) if ((n % 2) == 0) { // Recursive version: expt3(x.multiply(x), n/2, accumulator); n = n/2; x = x.multiply(x); } // n is even // If n is odd, subtract 1 from it and .. else { // Recursive version: expt3(x, n-1, x.multiply(accumulator)); n = n - 1; accumulator = x.multiply(accumulator); } // n is odd } // while return accumulator; } // exptWhile(BigDecimal, int) + O(n) + O(1) + O(log_2(n)) Looking at the data, we see that every time the input size (n) doubles, the running time goes up by a constant (2, in this case). Hence, the function is O(log_2(n)) Sequential search: Look at each element Homework: Try again writing the tests for sequential and binary search. * MAKE A NEW COPY OF Computer.java