CSC152 2005S, Class 30: Algorithm Analysis (2)

Admin:
* Cookies!
* Assignment due!
* Exam to be returned Friday.  (By special assignment from the president.)
* Homework for break:
  * Figure out a way to keep Rolf in check
  * Figure out a way to get the "East siders" to participate
  * Jonathan also must figure out how to get Sam to stop throwing things

Overview:
* Iterative efficient exponentiation
* Analyzing algorithms: Ignoring the details
* Analyzing algorithms: Big O notation
* Analyzing algorithms: In practice

Iterative Efficient Exponentiation:
* See sample code
* Natural conclusion: Recursion is your friend
* Other conclusions:
  * We can make recursive functions "iterative" (use while loops)
  * Accumulators help

Given two algorithms that solve the same problem, how do we 
determine which is "the fastest"?
* Experimentally/emperically: 
  Run lots of time tests on the two algorithms
  * Note: If we had only tried 100, 200, 300 as exponents, we would have preferred v3 (while) to v2 (recursive)
* Count the number of steps each algorithm will take "in the worst possible case"
  * Take the one that will be fastest
* We'll do both!  (The experiments will help support our counting)

More precisesly, we'll write a function f(n), that gives "the number
of steps the algorithm takes on input of size n"
* Problem: Some steps take longer than others
  * Addition almost always takes less time than multiplication
  * Multiplying really large numbers takes longer than multiplying small numbers (at least if you're using BigDecimals)
  * Multiplying floats or doubles takes longer than multiplying ints or longs
* Problem: The time an operation takes depends on the computer it runs on
* Problem: In experiments:
  * Two inputs of the same size may seem to take different times
  * The same input of the same size may seem to take different times
* Problem: Don't want to experiment with large inputs
  * Goal: Predict running time for large inputs
* The mathematician's solution: 
  * Ignore particular details (e.g. constant multipliers)
  * Predict the "shape" of the function

We'll use Lorelei's solution of "count the worst case" and then
throw away constant multipliers and smaller-order terms.

Formalisms:
* A function (typically the running time for a function) is in
  Big-O of g(n), represented O(g(n)), iff,
  * Exist c>0 and n0 s.t. for all but finitely many n > n0 |f(n)| <= |c*g(n)|
* Englishisms:
  * n>n0 "for big enough n"
  * c: "We don't care about constant multipliers"
* Related formalisms:
  * Theta(g(n))
    |f(n)| = |c*g(n)| for all but finitely many n > n0
  * little o
    |f(n)| > |c*g(n)| for all but finitely many n > n0

Our goal (in practice)
* Bound running time above 'closely'
* Accept approximations

Consider expt1, for (i = 0; i < n; i++) { result = result*x; }
  This is O(n), assuming that each multiplciation takes a constant time

Consider expt3, while (n > 0) ...
  At worst, in every-other repetition of the while, we split the exponent (n) in half
  2 * "number of times we have to split n in half to get 1"
  2 * log_2(n)
 But we can throw away the 2* (as well as the five or so steps in the body)
  O(log_2(n))

What do we do in general?
* For a simple statement (assignmet with some expression): Count 1
* For a conditional: Count both halves and take the max
* For a loop: Count (a) the number of times the loop repeats;
  (b) the time each repetition takes; Multiply those two values
* For a functional/procedure/method call: Look up the amount of time that function takes (or analyze separately)
* Finally: Add 'em all up

adfasdfjkl;
asdfasdf;
ash/
asdaghagg/
asdfasddf;
while a(adfasdf)
 a asdfasd;h;
 if (asdfasd)
   asdfasdf;
 else
  asdfashdfas;

Tomorrow: Examples!