Code written in class

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

Topics

• 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