Agenda/topics:

• Finish Sec 3.2 / 3.3:
  • review mathematical definitions (and intuitive understanding) of
    • “big-O” notation (upper bound)
    • “big-Ω” (big-Omega) notation (lower bound)
    • “big-Θ” (big-Theta) notation (both upper and lower bound)
    • “Big-O gives an upper bound on the growth of a function, while Big-Omega gives a lower bound. Big-Omega tells us that a function grows at least as fast as another.”
  • look at relevant video lectures/slides from Coursera Algorithms course
  • HW#4 exercises from Sec 3.2 & Sec 3.3

To Do:

• hand in Quiz #3: take-home quiz re linear search
• continue working on HW#4! due next Monday (May 16)

Boardshots:

TBA

Agenda/topics:

• Continued with Sec 3.2 & 3.3:
  • reviewed Monday’s material re time complexity of linear search, binary search
  • outlined some of the important computational complexity classes:
    • O(log n): logarithmic time
    • O(n): linear time
    • O(n log n): “linearithmic” time
    • O(n^2): quadratic time
    • O(n^m): polynomial time (for m > 0)
    • O(2^n): exponential time
  • introduced mathematical definition of “big-O” notation

To Do:

• Quiz #3: take-home quiz re linear search – due Monday (pdf available via Files)
• HW#4: work on Sec 3.1 & 3.2 exercises! Sec 3.3 exercises TBA

Boardshots:

Agenda/Topics:

• Begin Sec 3.3:
  • time complexity (running-time of algorithm as function of input size)
  • analyze time complexity of
    • max & linear search: O(n) [linear time]
    • binary search: O(log n) [logarithmic time]
• Refer to relevant concepts from Sec 3.2 (“The Growth of Functions”)
  • growth of different functions (see Fig 3, p223)
  • “big-O” and “Theta” notation (next time)

To do:

• continue working on HW#4 (due date TBA)
  • Sec 3.1 exercises listed on Homework page
  • Sec 3.2 & Sec 3.3 exercises TBA