F2021 CS 340 Lecture 11 (Amortized Analysis, Array Doubling/Resizable Arrays)

In today's class I introduce you to amortized analysis. We justify the practical consideration of doubling the size of an array when it is full! We do this using the aggregate method. The analysis given here is very general and can be used to justify many array-based data structure's amortized analysis.
Note: The 9th square I draw on the board in the last example should be blue!

Time Stamps:
0:00 Opening/Recap of Amortized Analysis
4:55 What is amortized analysis?
8:23 Warmup example, inserting into a sorted array
17:25 Visualization of the difference between two scenarios which both take linear time in the worst case, but seem to differ considerably!
22:50 Aggregate Method and Gameplan!
29:10 Example, Doubling an Array's Length!
52:23 (Geometric) Growth Factors