COMP 61: Discrete Math

Week 7, Thursday, February 27

• Covered: Theta notation
• Class notes (see full notes if you want to practice step-by-step; otherwise see condensed)
  • theta-condensed.pdf
  • theta-full.pdf
• Textbook sources
  • Scheinerman: chapter 5, section 29.
    Note that the defintions for big-O and big-Omega differ from what I gave in class. I assumed that functions are positive.
  • Introduction to Algorithms, 3rd edition, by Cormen, Leiserson, Rivest, Stein. Chapter 3 is much more in line with what I presented.
• Links
  You are not responsible for learning the following in this class. Stirling's approximation is useful in several scientific fields. You will see it applied in comp160 when the complexity of sorting is analyzed.
• Further comments
  • Understanding Theta notation now will make a huge difference when you take comp160, or any class involving algorithms.