CSC301.01 2015F, Class 04: Asymptotic Algorithm Analysis, Continued
===================================================================

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Questions.
* Asymptotic analysis, revisited.
* Other properties of Big-Oh notation.
* Careful loop counting.

Preliminaries
-------------

### Admin

* Many of you did not fill out the department course preferences survey.
  I may call on you individually.
* Please turn in your academic honesty forms if you have not done so
  already.
* My normal office hours are MWF 11:00-11:50.  You sign up for those at
  <https://rebelsky.youcanbook.me>.  My paperwork times are M-F, 8-9
  am.  Those are probably the best times to try to schedule alternate
  appointment times.  Check my schedule for more.  (I'll give up the
  occasional class prep time if necessary, but I prefer advance notice.)
* I know that some folks are having trouble doing 2-1.  We'll work on an
  example in class.

### Upcoming Work

* For Monday: No additional reading.
* For Wednesday: Problems 2-1, 2-2, 2-3, 2-8, 2-13, 2-14, 2-15, 2-18, 2-23, 
  2-32, 2-37, any two interview problems from chapter 2.  
    * Turn in *hardcopy*.
    * I prefer that you write your homework in LaTeX.  If you don't know 
      LaTeX, now is a good time to start learning!

### Extra Credit

#### Academic

* CS Table, *Tuesdays*, cellular network in developing communities
* CS Extras, Thursdays, topics forthcoming.
* Convo, Thursday, 11am.

#### Peer

* Men's Soccer, 5pm, 9/4 vs. Crown College
* Women's Soccer, 2pm, 9/5 vs. Simpson.

### Questions

Asymptotic analysis, revisited
------------------------------

* Big-Oh is used to indicate worst-case running time.
* Formal definition
        
        f(n) is in O(g(n)) iff exists c,n0 s.t. f(n) < c*g(n) for n>n0

* What role does the n0 serve?  "For large enough n"; it lets us ignore
  ugly stuff when n is small.  1000000000 + .0000001n
* What role does the c serve?  It lets us ignore constant multipliers.
  Instead of worrying whether it's 3n^2 or 2n^2 1.002n^2, we can just
  say O(n^2).
* Shows the upper bound of a function.
* Big O is interesting in many contexts, but as computer scientists we
  use it as a way to assess running time.
* Omega(g(n)) gives the lower bound
* Theta(g(n)) gives both upper and lower - tight bound!
* There are others; we will focus on these three.
* Also little-o

        f(n) is in o(g(n)) iff lim as n->inty f(n)/g(n) = 0

* Why have a formal definition of Big-Oh?
* Formality can help lead to accuracy.
* Formality lets us develop properties

Other properties of Big-Oh notation
-----------------------------------

* f(n) is in O(g(n)) and g(n) is in O(h(n)), what do we know
  about f vs. h?
    * f(n) is in O(h(n))
    * Proof: Need to find a c and n0 s.t. f(n) < c*h(n) for all
      n > n0.
    * What do we have as tools to find that n0 and c?
    * We know that exist d and m0 s.t. f(n) < d*g(n) for all n > m0
    * We know that exist e and n1 s.t. g(n) < e*h(n) for all n > n1
    * Let n0 = max(m0,n1), c=d*e
    * Do we know that f(n) < d*e*h(n) for all n > n0?
    * We know f(n) < d*g(n) for n>n0
    * f(n) < d*e*h(n) for n>n0
* f(n) is in O(h(n)) and g(n) is in O(h(n)), what do we know about
  (f+g)(n)?
    * (f+g)(n) is in O(h(n))
    * Proof
* f(n) is in O(h(n)) and g(n) is in O(i(n)), what do we know about
  (f+g)(n)?
    * (f+g)(n) is in O(h(n) + i(n))
    * 
* f(n) is in O(g(n)+h(n)) and g(n) is in O(h(n)).  What else do we know
  about f(n)?
    * f(n) is in O(h(n))

Careful loop counting
---------------------

<pre>
function conundrum(n)
  r := 0
  for i := 1 to n do
    for j := i + 1 to n do
      for k := i + j − 1 to n do 
        r := r + 1
  return(r)
</pre>