CSC152 2006S, Class 34: Algorithm Analysis (2): Formalizing the Notation

Admin:
* There are no readings for tomorrow.
* An eboard for yesterday is available.
* I was disappointed in some of you folks yesterday ...
  * that so few seemed to remember the efficient exponentiation algorithm.  
  * that a few of you seemed to be reading email during class.  (Note that it's a bad idea to do so when there's a faculty member right next to you.)
  * that so few of you participated
  * I was tempted to give you a quiz today.
* Today will continue the lecture/discussion model.  Tomorrow will be lab.

Overview:
* A better exponentiation function?
* Notes from yesterday.
* Asymptotic Analysis.
* Asymptotic Analysis in Practice.
* Supporting Asymptotic Analysis with Experiments.
* Eliminating Constants.
* Relating Functions.

Can you do better than the "divide and conquer" strategy for
exponentiation?

Rather than x^n = (x^(n/2))^2, do x^n = (x^(n/b))^b for
  some big number b

Let's try some examples

* Whoops , with 3 as b, it takes longer
* The problem is that, althoguh we divide the exponent more times, we also do more multiplications.
* Also, we'll still get log_something, which is not constant

The solution

x^n = e^nlnx

Moral: Sometimes you need to think "outside the box".
---

/Lessons from Monday/

* Many factors make an algorithm "good" or "better".  (In this course, we will often focus on efficiency.)
  * The problem domain also has a big effect.

* Cute facts
  * The compiler precomputes additions (and other arithmetic operations) when possible
  * Roller Coaster Tycoon draws 1000's of objects again and again

* When we compare the run-time efficiency of algorithms, we tend
to abstract away details so that you can compare them more
easily.
  * Constant multipliers and adders do not matter
* The Big-O thing is how we abstract away details.
* When we analyze algorithms, we can consider
  * Worst case
  * Average case
  * Best case

Analyzing Algorithms: Math, Science, and Engineering Approaches

Math: A formal definition of Big-O that supports "you can ignore multipliers and constant addition"
Engineering: Informally analyze the Big-O running time of an algorithm
Science: Experimental hypothesis verification

Formal definition - What do we want it to indicate?
* A focus on the shape of the run-time-vs-input-size curve, rather than particular details (such as multiplication factors)
* A sense that we don't care too much about how it behaves for small input sizes

O(g(n)) is a set of functions.
How to define sets
* List the elements: DaysOfTheWeek = { Monday, Tuesday, Wednesday, Thursday, Friday, Saturday, Sunday }
* Give equations that specify elements
  0 is in N
  if i is in I, then i+1 is in N
* Give a predicate that indicates whether or not a value is in the set

f(n) is in O(g(n)) if and only if
  Exist n0 and c such that
    for all n > n0, |f(n)| <= |c*g(n)|

Why is this useful?

* It helps us eliminate constant multipliers
  Compare f(n) = 0.5*n to g(n) = 100*n
  * Does big-O support the claims that f(n) is in O(g(n))
    and g(n) is in O(f(n))?
  * For any positive n, 0.5*n < 100*n, so let c=1 and n0 be 0
    => f(n) is in O(g(n))
  *  100*n <= c*0.5n as long as c>=200 and n>0
    => g(n) is in O(f(n))
  
* It helps us eliminate smaller-order terms
  Compare f(n) = n + 5 to g(n) = 2n
   n+5 <= 2n when  n>5 so, f(n) is in O(g(n))
   2n <= c*(n+5) when c is 2
  Similarly 2n is in O(2n+5)
  and 2n+5 is in O(2n)


The primary outcome for computer scientist: We can talk about the
running time without worrying about constant multipliers or
smaller order terms, and say O(n), O(n^2), O(logn) and not
something like O(3n+5)

How do we use big-O notation?
* We count the steps in a procedure
* We express the running time as a function of the input size
* We throw away constant multipliers and lower-order terms

Counting steps (worst case analysis):
* Arithmetic, Comparison, Assignment, I/O: 1 step
* Conditional: Maximum of the cost of the branches
* Loop: Count number of repetitions and cost of body, multiply
* Sequence of statements: Add 'em up
* Function call: Compute the cost of the called function

public int smallest(Comparable[] values)
{
   Comparable tmp = values[0];
   for (int i = 1; i < values.length; i++) {
     for (int j = i; j < values.length; j++) {
       if (!(values[i]  instanceof Integer) {
         throw new StupidUserexcpeiont();
       }
     } // for
     if (tmp.compareTo(values[i]) > 0) {
       tmp = values[i];
     } // if
   } // for
   return tmp;
} // smallest

About 5*n + 2 steps, O(n)