Previous Lecture

lect08

Next Lecture

lect08, Thu 04/24

Week 4: Space complexity, best/worst case analysis

Code from lecture

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

Lecture handout: https://docs.google.com/document/d/1LCYoeDyQSKzUBoYgfZPpSz3z9kvBjX7HHj7AB9Ekt1o/edit?usp=sharing

Topics

• Definition of balanced BST
• Analysis of code that involves std::set and iterators
• Best case and worst case analysis of BST operations, amortized analysis via aggregation.
• Define space complexity of an algorithm