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