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