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: