Calls with Jared and Youssef
Average Case Complexity: Expected Value / Weighted Average
Tight Lower Bound:
- argument from completeness
- argument from I/O
- other sophisticated arguments
Case Study: Matrix Multiplication
- naive
- no one knows the tight lower bound