5. Amortization: Amortized Analysis

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

[@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?

[@emmafoley8987]

The best explanation of potential amortization I've found!

[@pistachios2463]

41:41 potential method

[@hamiltonchevez8114]

literally came here for this, thanks

[@flo7968]

thank you so much haha

[@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

[@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.

[@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

[@radred3662]

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

[@intrinsic9585]

🙏

[@wetbarofsoap]

shoutout to sajin

[@hritikzurange]

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

[@es8336]

i dont understand shit i fucking hate computer science

[@forthrightgambitia1032]

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

[@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?

[@puffvayne]

Potential Method 42:20

[@arno.claude]

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

[@jawoo2228]

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

[@puffvayne]

Why there are chalks on my face?

[@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!

[@shivanshpachauri2855]

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

[@volkankaln4713]

This lecture makes me smell chalk.

[@chaitrakeshav]

This is too good!

[@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.

[@Sacheess]

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

[@LegolasSmith]

i think its like an "extra grade token"

[@luojihencha]

I feel I am so stupid...

[@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

[@ChrisLeeX]

40:27 That example went nowhere.

[@radhekrishanrathod9001]

why they are not using marker

[@sydneystriker5355]

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

[@ChrisLeeX]

25:15 Not the correct conclusion.

[@sudipandatta5371]

this is the most boring lecture of mit