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.

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

[Patrickblox]

This is the best fucking explanations I've ever seen. I've had lectures about this topic, read about it, and watched other videos about it. But I never understood it until I saw this video, and I understood it immediately on my very first watch. Awesome explanation, thanks!

[dorcyh.a]

Professors should just play this video when it comes to this topic. Very clear explanation loved it!!

[tebes]

Fantastic video with crisp and clear explanations. Helped me out so much, thank you!

[CreativeMathProblems]

Thanks a lot for this. Using this to save me in exams twice. I like how you go through examples clearly.

[Agrover]

I had watched the MIT OCW video on the same topic, although it gives a brief very swift overview, this video really cemented why? and how because you show us step by step!

[baddie]

to the point and concise, really helpful. thanks!!

[aadityasuman]

thank you so much very nice explaination...

[roopamtaneja]

Love the explanation for dynamic tables accounting method

[oguzcetin]

My analysis of algorithm teacher directly use your pdf to teach us.NO JOKE

[mohammadyahya]

Thank you very much for your effort. At 19:29, should not we get at 2: 0 0 0 0 1 1 0 please since we want to flip bits starting from A[2]?

[Agrover]

22:45 Could you share the proof/series which lead to it converging to 2 and henc UB <=2n?

[abdolrahimtooraanian]

Nice explanation, could you please share the slides?

[chunny__]

Would you be able to go over the potential method please?

[ll-bcgn]

Good vid. One question I have is, for the accounting method, if we already calculate the actual cost, whats the point of even thinking about the amortized cost? What is the benefit of using accounting method?

[Agrover]

Amortized Complexity got me thinking how is it different from Average Case Complexity?