Previous Lecture

lect09 Before Slides

lect09 Annotated Slides

Next Lecture

Code written in class

https://github.com/ucsb-cs24-s18/cs24-s18-lectures/tree/master/lec-09

Topics

• Run time of programs - why you should care?
• Challenges in measuring time efficiency and the pros/cons of different methods - absolute time, counting steps
• Measuring the impact of algorithms on running time (independent of implementation details/hardware/compiler….etc) - Count steps by detailed computer model of times to fetch, store, assign …
• O notation - Big Oh - asymptotic analysis and orders of growth, but also briefly Little O, Big Omega, Big Theta
• Formal Big O - formula and graphical presentation
• Complexity classes - constant, logarithmic, exponential, linear, quadratic, cubic
• Best case, worst case, average case

• Example algorithms

• Binary search in sorted arrays