Lecture 9/23/97
o Analyzing Running times
o Asymptotic analysis
o Order notation
o Examples

	Material in Chapter 6 of Standish
(You can pick up quiz1 in the course secty's office Wean 4116.
 For questions on the grading of the quiz, see Profs Blum or Goldstein.
 For questions on the grading of hwk1, see Craig Damon)
==============================================================================

SELECTING AN ALGORITHM

Often when you're going to write a program to do something, there are
several ways you might try to go about it.  Important things to consider:

	Is the approach correct?
	How fast does it run?
	How much memory does it use?
	Can I finish it in the next 8 hours?

Which of these are more important will depend on the circumstances.
Eg, if simple routine runs fast enough, not worth making complicated
for speed.

On the other hand, sometimes speed IS important, or sometimes the
simple method is just REALLY slow.  

Example:
Fibonacci numbers: 1 1 2 3 5 8 13,... fib(n) = fib(n-1) + fib(n-2).

Here is a naive program:
int fib(int n)
{
  if (n <= 1) return 1;
  return fib(n-1) + fib(n-2);
}

Turns out the number of function calls is more than fib(n) itself!


Given this, how much time would it take to run fib(100)?

Assume
  200 Mhz processor
  about 30 cycles/function call

  fib(n) = 1.618^n / sqrt(5) 
  fib(100) = 3.53 x 10^20  (300 quintillion)

  200 * 10^6 cycles/sec     * 86400 secs/day * 365 days/year
  30 cycles/fun call

  about 2*10^14 fun calls/year

  so it will take 3.5 * 10^20/ (2*10^14) = 1.7 million years  


The point is that naive algorithms can run very slowly.
It is therefore important to analyze performance and pick
out a good algorithm.

Today:  a framework for comparing different approaches. 

Main thing we want to look at is: How does the running time SCALE as
input gets larger?  Say we drew a graph running time vs. input size.
Want to know: what does the curve look like (ignoring low order terms)?

	r |                ?
	u |
	n |                         ?
	n |
	i |
	n |
	g |
	  |                                ?
	t |
	i |
	m |
	e |____________________________________
             input size (number of words in dictionary, etc.)

Basically 2 ways to tell shape.
  1.  Run on different sizes and time it, OR,
  2.  Look at program and count steps.  Advantage of this approach is can
      try and figure out WHY running time is the way it is.

ASYMPTOTIC ANALYSIS
-------------------
* Say each basic operation takes a CONSTANT amount of time.
  (+,*,=,==, a[], etc).

* Ask: how does running time SCALE with the input?  What is it
  PROPORTIONAL to?

Simple example:

// searching the array A for the key "key"
int linSearch(int A[], int n, int key)
{
  int i;
  for(i=0; i<n; ++i) {
    if (A[i] == key) return i;
  }
  return -1;
}

Say we call this on a key that is *not* in the array.  How much work
gets done?

* 1 assignment (i=0)
* n times we do:
     - comparison (i<n)
     - comparison and array reference (if (A[i] == key)...)
     - increment
* 1 more comparison (n<n)
* return.

Depending on the machine, these different basic operations may take
different amounts of time, but let's just abstract that away.
	
How does running time scale with input?  What's it proportional to?

Answer: running time is proportional to n, the size of the array.

Another example:

Creating a maze from a dictionary of n 5-letter words.

Suppose that our algorithm is to compare all pairs of words to see
if they differ in just one character:

      for (i=0; i < n; i++){
         for (j=i+1; j < n; j++){
            if (word[i] differs from word[j] in one character){
               add "i j" to the list of edges
               add "j i" to the list of edges
            }
         }
      }

--> time goes like: (n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1.
  
See if anyone knows the formula for this:  n(n-1)/2

--> Running time is proportional to n^2.

      P.S. We didn't do it this way!

---------------------------------------------------------------------


Instead of saying "proportional to" all the time (and to be a bit more
formal about what we mean), computer scientists have developed some notation.

Think of T(n) as running time of program on input of size n.  f(n)
some function like n^2, 

"O" notation:
T(n) = O(f(n)) if there exist two positive constants c and n_0 such that
               T(n) <= c*f(n) for all n > n_0

	[T(n) is AT MOST proportional to f(n)]

"Omega" notation:
T(n) = Omega( f(n) ) if there exist two positive constants c and n_0
                     such that T(n) >= c*f(n) for all n > n_0

	[T(n) is AT LEAST proportional to f(n)]

"Theta" notation:
T(n) = Theta( f(n) ) if it is both O(f(n)) AND Omega(f(n)).

	[T(n) IS proportional to f(n) in the limit]


EXAMPLES:
     n^2 + n = O(n^2)       < 3*n^2
     
     4n + 5 + 3*sqrt[n]?  = O(n)    Are these THETA too?     

Can also think of it this way:

Consider the limit of this ratio, and what happens to it:

                           infinity                 --> CASE A
   lim T(n) / f(n)     ==  number > 0 (e.g., 17)    --> CASE B
  n->inf                   0                        --> CASE C

CASE B or C: T(n) = O( f(n) ) - i.e., at most proportional

CASE A or B: T(n) = Omega(f(n)) - i.e.,at least proportional

In the overlap (CASE B): T(n) = THETA( f(n) ).

(Note that if the limit does not exist, it's still possible
that T(n) = O(f(n)), or T(n) = Omega(f(n)), or T(n) = Theta(f(n)), e.g.,
T(n) = n sin n is Theta(n).)


Why not just have Theta?  One reason is that sometimes it is hard to
calculate exactly.  Easier to give upper bound or lower bound.

Or, you might want to say:

"ANY algorithm for problem foo must take Omega(n log n) time in the
worst case.   My fancy algorithm takes time O(n log n).  Therefore, my
algorithm is a good one."


MORE EXAMPLES:
       2n^3 + 100 n^2 + 17 n + 3 = O(WHAT?)  Is it Theta(n^3) --> yes.

       --> limit T(n) / f(n) = 2.

       Is it O(n^4)?
       --> limit T(n) / f(n) = 0.

       Is it O(n^2)? No. lim is Infinity.




Here's a different recursive alg. for fib:  Pretty neat.  if you
understand this, it will help you out in 15-212.

int fib(int n)
{
  return rec_fib(1, 1, 1, n);
}

int rec_fib(int old, int current, int i, int n)
{
   if (i >= n) return current;
   else return rec_fib(current, old+current, i+1, n);
}


Do  rec_fib(1, 1, 1, 5)

What is running time?   Answer: O(n).