Notes on Recurrence relations and complexity analysis:


The analysis of algorithms can be very mathematical.  For the purpose of
our class, I have decided that I expect you to understand the following:


I.  Be able to write down a mathematical formula representing the running
    time of a program.  For example, we saw how to do this for bubblesort.
    This includes writing down recurrence relations.


II. Memorize the solutions of the following six recurrence relations:

    Recurrence Formula			Complexity class

    1. T(n) = T(n/2) + C		lg(n) (logarithmic)

    2. T(n) = T(n-1) + C		n  (linear)

    3. T(n) = 2*T(n/2) + C		n  (linear)

    4. T(n) = 2*T(n/2) + C*n		n*lg(n)  ("n log n")

    5. T(n) = T(n-1) + C*n              n*n (n squared - polynomial)
    
    6. T(n) = 2*T(n-1) + C		2^n (exponential)
   
You don't have to be able to derive these forms yourself, but you should
at least memorize them, for these are common forms that can be given to
many algorithms.  Note that the differences between these formulas can
be subtle in appearance, but the differences are tremendous.  


III. Understand how these relations represent the average and worst
     case complexities of typical algorithms.  Here are examples of
     algorithms for each of the six forms:

    1. binary search 
        (worst-case for sorted arrays, average case for binary trees)

	Recurrence relations do NOT necessarily only represent recursive
	programs.  For example, binary search is an algorithm that can
	be implemented with a while loop just as easily as with recursion,
	but the complexity classification is the same.  

    2. iterative (tail-recursive) fibonacci function (or any common loop).
       
    3. sum of the numbers of a binary tree (average case).  Many algorithms
       on binary trees can be written with two recursive calls, on the 
       left and right subtrees.  Many of these algorithms will have a
       recurrence relation of this form. 

    4. worst case heapsort, mergesort, average case quicksort.  This
       very important relation can be given to many of the most important
       algorithms in computer science, including the "fast Fourier transform",
       which is "fast" because the regular version is n*n instead of n*lg(n)

    
    5. worst case quicksort, bubblesort

    6. naive fibonacci (fib(n) = fib(n-1) + fib(n-2)).  This function's
       behavior is caused by redundant computation, not by "making too
       many recursive calls".  Most of the algorithms of form 4 - n*nlg(n) -
       also make multiple recursive calls.  Also, algorithms that 
       must exhaustively enumerate all possible solutions often will have
       this form.  A complexity class that's also exponential is n! 
       (n-factorial).  An algorithm that has to search through all possible
       permutations of some string, for example, will have O(n!) time and
       thus also exponential.