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) < ch(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) < dg(n) for all n > m0
  • We know that exist e and n1 s.t. g(n) < eh(n) for all n > n1
  • Let n0 = max(m0,n1), c=de
  • Do we know that f(n) < deh(n) for all n > n0?
  • We know f(n) < d*g(n) for n>n0
  • f(n) < deh(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

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)