5. Amortization: Amortized Analysis

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

[@emmafoley8987]

The best explanation of potential amortization I've found!

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

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

[@rohitnagare7634]

14:02 Accounting method

[@pistachios2463]

41:41 potential method

[@hamiltonchevez8114]

literally came here for this, thanks

[@flo7968]

thank you so much haha

[@hritikzurange]

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

[@puffvayne]

Potential Method 42:20

[@forthrightgambitia1032]

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

[@radred3662]

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

[@intrinsic9585]

🙏

[@wetbarofsoap]

shoutout to sajin

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

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

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

[@arno.claude]

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

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

[@AdamOwolabi-p2y]

This is so good.

[@Sacheess]

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

[@LegolasSmith]

i think its like an "extra grade token"

[@sydneystriker5355]

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

[@chaitrakeshav]

This is too good!

[@jawoo2228]

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

[@ChrisLeeX]

25:15 Not the correct conclusion.

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

[@volkankaln4713]

This lecture makes me smell chalk.

[@ChrisLeeX]

40:27 That example went nowhere.

[@puffvayne]

Why there are chalks on my face?

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

[@radhekrishanrathod9001]

why they are not using marker

[@luojihencha]

I feel I am so stupid...

[@shivanshpachauri2855]

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

[@es8336]

i dont understand shit i fucking hate computer science

[@sudipandatta5371]

this is the most boring lecture of mit