Amortized Analysis: Aggregate Analysis and Accounting Method
I introduce the aggregate analysis and accounting method by the examples of multi-pop stack, binary counter and inserting into a dynamic array.
There is also a follow-up video on the potential method for amortized analysis: • Potential method for amortized analysis
0:00 Multi-pop stack
4:50 Amortized Analysis
5:53 Multi-pop stack: aggregate analysis
9:23 Multi-pop stack: accounting method
17:57 Binary Counter
20:32 Binary Counter: aggregate analysis
24:00 Binary Counter: accounting method
29:40 Dynamic Arrays
32:45 Dynamic Arrays: accounting method