5. Amortization: Amortized Analysis

MIT 6.046J Design and Analysis of Algorithms, Spring 2015
View the complete course: 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 ocw.mit.edu/terms
More courses at ocw.mit.edu

[@emmafoley8987]

The best explanation of potential amortization I've found!

[@alexandrebrownAI]

Timestamps:
- 0:20 : Introduction, Usefulness of Amortized Analysis
- 1:41 : Table Doubling Problem with Intuition on Amortized Cost
- 5:42 : Aggregate Method
- 7:18 : General Definition of Amortized Bounds
- 14:02 : Accounting Method
- 22:22 : Table Doubling Problem using Accounting Method
- 27:57 : Charging Method
- 31:00 : Table Doubling Problem using Charging Method
- 42:11 : Potential Method
- 48:52 : Binary Counter Problem using Potential Method
- 56:00 : Insert in 2-3 Trees using Potential Method
- 1:04:21 Insert & Delete in 2-5 Trees using Problem Method

[@imprsnt]

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

[@samiere]

referencing @2:30

[@dylancutler1978]

I was wondering about that. In his analysis table doubling would have increased the runtime complexity, this makes more sense.

[@alisalloum2005]

You saved my life

[@Jayveersinh_Raj]

@@alisalloum2005 Helloo Buddy!! XD

[@gshengelaia2001]

so there is an error in the video right?

[@pistachios2463]

41:41 potential method

[@hamiltonchevez8114]

literally came here for this, thanks

[@flo7968]

thank you so much haha

[@forthrightgambitia1032]

Interesting, I studied B-trees at uni and they presented the 2, 5 tree without justification of those numbers. But here it is.

[@DenisG631]

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

[@MrLala12321]

It's possible the log(n) is referring to the rebalancing of the tree(which wouldn't happen if the element didn't exist) and not the searching for the element. Otherwise you're correct.

[@rohitnagare7634]

14:02 Accounting method

[@user-tk2jy8xr8b]

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?

[@junzhai1715]

as long as the coin value is constant, O(1), it is fine, not necessary "once", could be 2,3,4...
The point is that the cost of copying n elements charges 2 * n/2. we can save those n/2 coins with value 2 during each of the n/2 element's insertion.
In contrast, we cannot save coins with value O(n), because that will make the insertion not O(1) anymore.

[@hritikzurange]

thanks for the charging method, makes life much easier :)

[@avoriginal9342]

so for the accounting method you are adding 2 coins for each insertion, 1 insertion costs 1 coin and you store one to be able to pay for the deletion?

[@chaitrakeshav]

This is too good!

[@puffvayne5688]

Potential Method 42:20

[@ChadieRahimian]

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

[@ChadieRahimian]

I have. Even all the other lectures of 6.046.

[@TroyWhorten]

Chapter 17 from CLRS? The potential method in particular was pretty fuzzy for me from just the lecture but the description in the book really brought it together.

[@ChadieRahimian]

Troy Whorten yeah I'm having a hard time understanding the concept of amortization. I guess I need to go through that chapter of the book couple more times 😁

[@miro-miro-on-the-wall]

oof get out of here with your misogynistic bs

[@radred3662]

shoutouts to any students at uvic cramming for an exam right now

[@intrinsic9585]

🙏

[@wetbarofsoap]

shoutout to sajin

[@JuanSanchez-yi1wn]

At 39:00 Can I use this for Crypto asset valuation? Specifically BTC since BTC white papers solves double spending problem

[@bhavyagor5366]

hey pls connect with me, i have a serious blockchain project to make

[@arno.claude]

11:08 why did he throw that frisbee? :D is it a reward for answering a question correctly? :D

[@puffvayne5688]

Why there are chalks on my face?

[@sydneystriker5355]

The last lecture was so hard that this lecture seemed piece of cake. :)

[@jawoo2228]

huhuhhh, yeahhhhh... Mr Van Driessen's cool...

[@volkankaln4713]

This lecture makes me smell chalk.

[@radhekrishanrathod9001]

why they are not using marker

[@Sacheess]

51:44 does he give frisbees for answers? So fucking cool.

[@LegolasSmith]

i think its like an "extra grade token"

[@shivanshpachauri2855]

i feel Eric to be too less energetic in this video.

[@thinkweb2]

I love Eric's explanations but this one felt way too theoretical. I wish he started with examples and used these techniques before diving into nitty gritty.

[@luojihencha]

I feel I am so stupid...

[@hossein_haeri]

Misleading words... Hard to get the core concept... I kinda think those people sitting there already knew the concept which is no surprise at MIT!

[@ChrisLeeX]

25:15 Not the correct conclusion.

[@ChrisLeeX]

40:27 That example went nowhere.

[@es8336]

i dont understand shit i fucking hate computer science

[@sudipandatta5371]

this is the most boring lecture of mit