5. Amortization: Amortized Analysis


MIT 6.046J Design and Analysis of Algorithms, Spring 2015

View the complete course: http://ocw.mit.edu/6-046JS15

Instructor: Erik Demaine

In this lecture, Professor Demaine introduces analysis techniques for data structures, and the implementation of algorithms based on this analysis.

License: Creative Commons BY-NC-SA

More information at http://ocw.mit.edu/terms

More courses at http://ocw.mit.edu

Topics:  Knowledge
Денис Меньщиков 

I got the idea of amortization in general, but these coins are totally weird. Why the heck do we charge back in time only once per insertion?


Very hard to understand. I rewound it so many times and takes some hours. Another short lecture was helpful to understand this.


Denis Grebennicov 

11:51 But that's not entirely true, since you can "try" removing an item, which is not in the tree, which will still cost O(logN) in order to look for the item, which is missing.

Correct me if I'm wrong

Chris Lee 

40:27 That example went nowhere.

Chris Lee 

25:15 Not the correct conclusion.


말총머리 핵간지

Shadi Rahimian 

This is the only data structure lecture of MIT, I didn't understand a word of :((

Prashant Barnawal 

Load Factor = number of Elements / Size of table = n / m.