Previous Lecture

lect02

Next Lecture

lect02, Thu 04/03

Week 1: Running time analysis

Code from lecture

https://github.com/ucsb-cs24-s25/cs24-s25-lectures/tree/main/lect02

Lecture prereading

• OP (Open data structures book), chapter 1.3: https://opendatastructures.org/ods-cpp/1_3_Mathematical_Background.html
• DG (Algorithms by Das Gupta): chapter 0.1 - 0.3 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf

  Topics

• Discuss and motivate runtime analysis
• Model of computation (constant time operations)
• Definition of Big-O and Big-Omega and why each is useful