15-451 Algorithms		1/14/99
* Basic	issues:					Handout:
   -asymptotic analysis			          - Homework 1. Due: Jan 26
   -worst-case/average-case/...				at start of class
* Recurrences
   - solving directly
   - helpful formulas

[Changes in TAs and office hour times from handout - see web page]
[Help session: Thurs at 7:00 in DH2210 starting next week]
--------------------------------------------------------------------------

Interested in running time of algorithms.

   - analyze in terms of size of input.  Use "n" for input size typically.

2 fundamental issues:

1. How detailed do we want to get?  What do we want to focus on?
	Focus on the how does running time *scale* with the input size.
- called "asymptotic analysis"
- idea is: ignore low-order terms, constant factors (which
	includes issues like how much does comparison cost versus getting an 
	array value), and look at running time as a function of n in the limit
	as n gets large.

- to do this, have convenient notation: O, Theta, Omega, little-o.

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) is 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)]

E,g, 3n^2 + n is O(n^2).  5n is O(n^2) and is also O(n).

Formally, should really write $T(n) \in O(f(n))$. Really O(n^2) is a set
of functions, and the definition above is telling us which functions
are in the set.  But, convention is to write T(n) = O(f(n)), which is
a little confusing.  If its gets confusing to you, use \in.

	Typical use: running time T(n) <= [blah] <= 3n^2 + 5n - 2 = O(n^2).

"Omega" notation:
T(n) is 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)]

	E.g., we'll prove that any comparison-based sorting
	algorithm must take Omega(n log n) in worst case.

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

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

	E.g., running time of mergesort is Theta(n log n).

"little-o" notation:
T(n) is o(f(n)) if for all c > 0, exists n_0 s.t. T(n) < c*f(n) forall n>n_0 

	[T(n) is LESS THAN proportional to f(n)]

	E.g., can you multiply two n-bit numbers is o(n^2) time?



EXAMPLES:
     100 n^2 log(n) + 2n^3 + 17 n + 3 = Theta(what?)

Often helpful to think of the notation 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

CASE B: T(n) = THETA( f(n) ).

CASE C: T(n) = o(f(n)).

CASE A: T(n) is little-omega(f(n)).  We won't be using this much.

E.g., limit of [2n^3 + 100 n^2 log(n) + 17 n + 3]/n^3
	
	= 2 + lim[(100log(n)/n + 17/n^2 + 3/n^3] = 2.
	
E.g., How do nlog(n) and n^{1.5} relate?  
	ratio is log(n)/sqrt{n} = sqrt{(log n)^2/n}, which goes to 0.

	So, nlog(n) is o(n^{1.5}).

The limit version is easier, but if the limit does not exist, it's
still possible that T(n) = <blah>(f(n)). E.g., T(n) = n(2+sin(n)) is
Theta(n), because it stays between n and 3n.

This notation gives us a language for talking about desired or
achievable specifications.  For example a typical use might be "we can
prove that *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 asymptotically optimal."

Fundamental issue 2:

Often running time is different for different inputs of the
same size.  E.g., quicksort where we pivot on the first element.
[remind how quicksort works.  Do example: {3 1 2 5 4}]

	- worst-case time = MAX, over inputs I of size n, of running time on I

	- average-case time (with respect to some distribution on inputs)
		Average, over inputs I of size n, of running time on I.

	- for randomized algorithm, worst-case expected time
		MAX, over inputs I of size n, of E[running time on I]

	  We'll talk more about this next class, but why might this be
		preferable to "average case"?

E.g., quicksort with first element as pivot on input of size n has
worst-case running time of Theta(n^2), average-case running time (over
uniform ordering of inputs) of Theta(n log n).  If we randomize the
algorithm by picking a random element as pivot,  we get for any
input I of size n, an expected running time of Theta(n log n) [And, in
fact, we get this "with high probability"]

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

Recurrences

We often are interested in algorithms expressed in a recursive way.
When we analyze them, we get a recurrence: running time on input of
size n, as a function of n *and* running time on inputs of smaller sizes.

- examples of recurrences

   Mergesort: To sort an array of size n, we sort left half, sort
	right half, then merge the two results. We can do the merge in
	linear time.  So, if T(n) is running time on input of size n,
	what recurrence do we get?   T(n) = 2T(n/2) + cn 

   What about base case?  Here, if the array has 0 or 1 elements, we just
	return.  In general, base cases almost always of the form "If n is
	less than <some constant - like 2, 5, 10> then do brute force which
	takes a constant amount of time".  If not specified, assume this is
	the base case.  Usually enough to say T(1) = c.

   What about "integrality" issue?  Some discussion in book.  We'll
	basically ignore it, knowing (having thought it through) that it
	doesn't matter.

   Selection sort: run through array finding smallest. Put in leftmost
	position. then recursively sort A[2..n].  What's the recurrence?
			T(n) = cn + T(n-1).

   Multiplication: we split into left and right halves.  Straightforward
	way to solve the subproblems gave us: T(n) = 4T(n/2) + cn.  But,
	rearranging terms in a tricky way improved this to T(n) = 3T(n/2) + cn.


How do we solve these?  Give 4 methods.
- solving by unrolling
- solving by guess and inductive proof
- solving by building recursion tree
- helpful "master" formula

1. solving by unrolling

   Many times, the easiest way to solve is to unroll the recurrence, to
	get a summation.   E.g., the one for selection sort gives us:

	T(n) = cn + c(n-1) + c(n-2) + ... + c = Theta(what?)

   What about T(n) = n^5 + T(n-1)?

		Solves to Theta(n^6).  Can see "O()" since we have n
		terms, each of which is at most n^5.  Can see
		"Omega()" since if we look at the top n/2 terms, each
		of them is at least (n/2)^5

   [More summations in Chapter 3 of book]
   [BTW, Today's material is in Chapters 2,3,4 of the book]


2. solving by guess and inductive proof.

   Say we have a recurrence T(n) <= 7T(n/7) + n, T(1) = 1.
	Guess #1: T(n) <= n*log_b(n).  Oops - doesn't handle base case.
	Guess #2: T(n) <= n*log_b(n)+g(n), where g(1) >= 1.  Assume true
	inductively.  

	This means that T(n) <= 7*[(n/7)*log_b(n/7) + g(n/7)] + n.
	Now, set b=7.  
	How can we simplify log_7(n/7)?  log_7(n/7) = log_7(n)-1. So we get:

		T(n) <= n*log_7(n) - n + 7*g(n/7) + n

	Just need 7*g(n/7) <= g(n) and g(1) >= 1. Suggestions?  g(n) = n works.
	So, this "guess" holds true inductively.  Therefore,

		T(n) <= n*log_7(n) + n = Theta(n log n).

    Important to be careful.  Here is a "proof" that the answer is O(n).
	See if you can tell where it goes wrong:

        Guess: T(n) <= c*n, where c >=1 to handle the base case.
	Assume true inductively.  This means that can plug into the recurrence:

		T(n) <= 7*[cn/7] + n
		      = cn + n
		      = Theta(n).

3. solving by building recursion tree

Mergesort recurrence: do cn work, plus recurse on two problems of size n/2.

      problem size	    time spent		add up row-wise
          n			cn		    cn
		              /    \
          n/2               cn/2   cn/2		    cn
                            / \     / \
          n/4           cn/4 cn/4 cn/4 cn/4         cn
           .
           .
           .
           1           c...................c        cn

log_2(n) levels, so result is Theta(n log n).

[[[ENDED HERE... DO REMAINDER NEXT TIME]]]

Fast multiplication recurrence:  T(n) = 3T(n/2) + cn

      problem size	    time spent		add up row-wise
          n			cn		    cn
		            /    |  \
          n/2             cn/2  cn/2 cn/2	    3(cn/2)
                          /|\   /|\  /|\
          n/4           cn/4 ...........cn/4        9(cn/4)
           .
           .
           .
           1           c...................c        3^{log_2(n)}*c

    Now, we notice that this sum is dominated by the bottom element: every
    time we take a step *up*, we divide by 3 and multiply by 2, so we get
    3^{log_2(n)}*c*(1 + (2/3) + (2/3)^2 + ...) and this summation is a
    convergent series.  (for r < 1, 1 + r + r^2 + r^3 + .... = 1/(1-r)).


    So, answer is Theta(3^{log_2(n)}).  We can rewrite 3 as 2^{log_2(3)},
    and then pull the "n" down.  So this is the same as:

		Theta(n^{log_2(3)})

"Master Formula"
 -------------

   We've seen a lot of recurrences that look like this:
			T(n) <= a*T(n/b) + cn.
   where a,b are constants.

   Let's solve this in general. [book does even more general case by
	replacing cn with f(n) on p.67.  Students should take a look]


   We just get the same tree as before, but replacing
		3 by a,
		2 by b.

   So, we get a summation of:

	cn[1 + a/b + (a/b)^2 + (a/b)^3 + ... + (a/b)^depth]

	where depth = log_b(n).

   Case 1: What if a<b? 
	sum is a convergent series.  Sums to at most 1/(1 - a/b) = const
	==> Theta(n).

   Case 2: What if a=b? 
	all terms in sum are equal to 1. ==> Theta(n log n).

   Case 3: What if a>b? 
	Again this is a geometric series, but now the last term is largest
	Easier to see if we reverse the order:

	  cn(a/b)^depth [1+ b/a + (b/a)^2 + ... + (b/a)^depth]

	Now the summation is a constant.

	Result is Theta(n*(a/b)^(log_b n)) 
		
		= Theta(a^{log_b(n)})

		= Theta( (b^{log_b(a)})^{log_b(n)} )

		= Theta( n^{log_b(a)} )