Recitation 9/24/97
o Analyzing running time
o Order notation
o Getting a feel for running times of programs

-------------------------------------------------------------------------
Let's do some more examples of figuring out the running time  of
programs. 

void foo(int A[], int n)
{
  for(int i=0; i < n; ++i) {
    int min = i;
    for(int j=0; j < n; ++j) {
      if (j > i && A[j] < A[min]) min = j;
    }
    swap A[i] and A[j]
  }
}

(This is a slow sorting algorithm)

Find running time:

* First we initialize i to zero.

* outer loop runs n times.  On each run:

  - do a constant amount of work (set min=i. set j=0. etc.)

  - inner loop runs n times.  On each run:

      do a constant amount of work

  - then do a constant amount of work to swap.


So, running time T(n) = c1 + c2*n + c3*n^2, for some constants c1, c2, c3 > 0

Let's describe this using O(), Omega(), and Theta() notation.

The basic idea is we toss out the low-order terms and ignore
constants.  So, we would say that this is Theta(n^2).

More formally:

Let f(n) be some function we're trying to compare our running time to.
What we do is look at the limit of the ratio T(n)/f(n) as n goes to infinity:

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

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

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

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

				     c3*n^2 + c2*n + c1
			 lim        -------------------
		     n-->infinity        n^2

By algebra this is


				         c2     c1
			 lim        c3 + --- + ---      =    c3
		     n-->infinity        n     n*n


So, we're Theta(n^2).

(Note that if the limit does not exist,  e.g., T(n) = n sin n, then
you need to go back to the full formal definition from lecture. E.g.,
in this case we would say T(n) = Theta(n).)

[If students ask, you can say that "little-oh" is for CASE C only, and
"little-omega" is for CASE A only, but we won't use these in this class]


Another couple examples

void f(int n)
{
  for(int i=0; i < n; ++i) {
    .. some constant-time stuff..
  }
  for(int i=0; i < n; ++i) {
    for(int j = i; j < n; ++j) {
       .. some constant-time stuff..
    }
    for(int k=i; k < n; ++k) {
      .. some constant-time stuff..
    }
  }
}

Answer: theta(n^2).

void g(int n)
{
  for(int i=0; i<n; ++i) {
    for(int j=i+1; j<n; ++j) {
      for(int k=j+1; k < n; ++k) {
         ..constant time stuff..
      }
    }
  }
} 

It's not too hard to see that the function takes AT MOST c*n^3 time,
since there are three nested loops.  So, this proves it is O(n^3).

To show it is Omega(n^3) we need to argue that it takes AT LEAST c*n^3
time for some constant c.

One way to do that is to draw a 3-D graph, with "i" as one axis, "j"
as another axis, and "k" as the third axis.  If you then look at all
the different (i,j,k) triples that are examined, they form a pyramid
that takes up 1/8 of the volume of the n x n x n cube.

===================================================================
Some common running times:  (Maybe plot these roughly on the board)

   O(1): constant time.  Time doesn't depend on size of input. 
	Examples: Inserting into queue, if you did it the fast way. 
		  Accessing a given element of an array.

   O(log n): logarithmic time.
	Examples: (ASK) binary search in a sorted array.

	Logarithmic time means that if input size doubles, the time
	only goes up by a constant.  
	What, roughly, is log_2(1000)? log_2(1 million)?  log_2(1 billion)?

   O(n): linear time.
	Examples: (ask)

   O(n log n):  we'll see examples of this later.  Almost linear.

   O(n^2): quadratic time.
	Examples: selection sort.

   O(a^n): exponential time.
	Examples: the really slow fib().

	Running time can double if you increase input size by a constant.
		2^{n+1} = 2*2^n.
	Even if you get a machine that's twice as fast, you can only
	handle a constant number more inputs.

   O(n!): even worse!
	(The only program I've seen with this kind of running time was
	a sorter written in prolog)

Another way to look at these:  say you can do 1 million ops/second.
Then, on an input of size 1 million, 

if T(n) = 1         then the total time is:  1/1,000,000 seconds
   T(n) = log_2(n)                        :  1/50,000 seconds
   T(n) = n                               :  1 second
   T(n) = n*log_2(n)                      :  20 seconds
   T(n) = n^2                             :  10 days
   T(n) = n^3                             :  35,000 years
   T(n) = 2^n                             :  forget it

(more tables like this in Chapter 6)