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
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.
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.
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.
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 😁
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.
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
The best explanation of potential amortization I've found!
Load Factor = number of Elements / Size of table = n / m.
referencing @2:30
I was wondering about that. In his analysis table doubling would have increased the runtime complexity, this makes more sense.
You saved my life
@@alisalloum2005 Helloo Buddy!! XD
so there is an error in the video right?
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
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.
14:02 Accounting method
41:41 potential method
literally came here for this, thanks
thank you so much haha
Interesting, I studied B-trees at uni and they presented the 2, 5 tree without justification of those numbers. But here it is.
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?
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.
thanks for the charging method, makes life much easier :)
Potential Method 42:20
This is the only data structure lecture of MIT, I didn't understand a word of :((
I have. Even all the other lectures of 6.046.
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.
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 😁
oof get out of here with your misogynistic bs
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?
11:08 why did he throw that frisbee? :D is it a reward for answering a question correctly? :D
shoutouts to any students at uvic cramming for an exam right now
🙏
shoutout to sajin
At 39:00 Can I use this for Crypto asset valuation? Specifically BTC since BTC white papers solves double spending problem
hey pls connect with me, i have a serious blockchain project to make
This is so good.
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!
This is too good!
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.
Why there are chalks on my face?
huhuhhh, yeahhhhh... Mr Van Driessen's cool...
25:15 Not the correct conclusion.
i feel Eric to be too less energetic in this video.
The last lecture was so hard that this lecture seemed piece of cake. :)
51:44 does he give frisbees for answers? So fucking cool.
i think its like an "extra grade token"
40:27 That example went nowhere.
why they are not using marker
This lecture makes me smell chalk.
I feel I am so stupid...
i dont understand shit i fucking hate computer science
this is the most boring lecture of mit