Amortized Analysis

[@caseyli5580]

More helpful than a 3 hour lecture. Thank you so much! Subscribed.

[@NERDfirst]

Hello and thank you very much for your comment and support! Very happy to be of help :)

[@KongLodden]

You just managed to explain in 20 minutes, what my professor could not in 2 hours. Best video I've seen on the topic.

[@NERDfirst]

Hello and thank you very much for your comment! Glad to be of help =)

[@MartianPotato]

I sincerely appreciate this content! I am taking an online class that is pure textbook reading and it's murderous. This video seriously saved me from hours of pain and suffering.

[@NERDfirst]

Hello and thank you very much for your comment and support! Very happy to be of help, all the best for your class =)

[@victoriajones8969]

I was really struggling with some very dry literature on amortised complexity for my data science degree and this has helped a huge amount. Great work :)

[@NERDfirst]

Hello and thank you very much for your comment! Very happy to be of help =)

[@shashwathbhaskar673]

i had been trying to find good material for this topic and reading for different sources but couldn’t understand anything and then I came across your video and now have no doubts. thanks bro

[@NERDfirst]

Hello and thank you very much for your comment! Very happy to be of help =)

[@madanielmadaniel]

Dude, thanks a lot ! Your explanations are a zillion time more clearer than the best University professor :)

[@NERDfirst]

+Daniel Madar Hello and thank you very much for your comment! That's great to hear, that means I've achieved what I've set out to do :)

[@stevennery233]

This was such an excellent video. Thank you

[@NERDfirst]

You're welcome! Very happy to be of help =)

[@TamilSelvan-xf6ut]

OMG this' the best amortized cost analysis lecture I've ever seen

[@NERDfirst]

Hello and thank you very much for your comment! Glad you liked the video!

[@marcc1179]

The best explanation of these 3 methods on the Internet! I watched a Corsera video but I did not get the point. Your video is more intuitive and clear! Thank you very much!

[@NERDfirst]

You're welcome! Very happy to be of help =)

[@garrettsmith2256]

I'm studying for finals, and this was SUPER helpful. Thanks!

[@NERDfirst]

You're welcome! Glad to be of help and all the best for your finals =)

[@sinaazartash3566]

Best video on youtube that explains amortization analysis so far.

[@NERDfirst]

Hello and thank you very much for your comment! Glad you liked the video =)

[@killerdoml7648]

Im so grateful for this video! Thanks for explaining that topic so well. It was kompact, but every important detail was mentioned. Chapeau!

[@NERDfirst]

You're welcome! Very happy to be of help and I'm glad you found it useful =)

[@anabelsa]

You look so young, and yet you are better at teaching than most professors. THANKS!!!!!!!!

[@NERDfirst]

Hello and thank you very much for your comment! Really appreciate the kind words! Very happy to be of help =)

[@Aiyara_AoC]

Wholesome and amazing explanation, thank you ! I finally understand the bank account method which my professor and the MIT 6.046 video failed to make me understand. keep up with the amazing content !

[@NERDfirst]

Hello and thank you very much for your comment! Very happy to be of help =)

[@priyankitanwar3491]

I genuinely cannot thank you enough for this! Thanks a lot man, thanks a lot :)

[@NERDfirst]

You're welcome! Very happy to be of help =)

[@justusmzb7441]

Because of Corona my Algorithm & Data-Structure lecture was severely downgraded, and a lot of subjects were not covered... Thanks to you, i can still get some of that knowledge.

[@NERDfirst]

Hello and thank you very much for your comment! Glad to be able to fill in that role for you =)

[@qkunder]

Your example is surprisingly similar to the question I got in my assignment, just worded differently, which helped me to look at it from dynamic array perspective. Thank you a lot!

[@NERDfirst]

Hello and thank you for your comment! Array expansion is a classic example for amortized analysis, so I'm not surprised! Glad to be of help =)

[@pruthvirajjadhav4049]

Best explained video ,I searched for shorter videos on this concept but they didn't explain in easy way .I wish I had watch this before❤

[@NERDfirst]

Hello and thank you for your comment! Very happy to be of help =)

[@lee-3-]

You're better than my professor !!! thank you so much

[@NERDfirst]

You're welcome! Very happy to be of help =)

[@yapchengyee953]

Cool explanation on the intuition of amortized analysis :D the rough idea does helps a lot in the understanding of the topic. Thank you very much

[@NERDfirst]

You're welcome! Very happy to be of help :) What remains is to apply!

[@siddarthathentu689]

Just amazing. What a great explanation! You just earned a subscriber.

[@NERDfirst]

Hello and thank you for your comment and support! Glad you liked the video =)

[@skittles6486]

Wow. Wow wow wow wow wow wow wow wow wow wow...... I am speechless. Just speechless. You are a genius. Best video on this topic. I want to give this video 1 million likes.

[@NERDfirst]

Hello and thank you very much for your comment! Very happy to be of help =)

[@abhishekravoor]

This was the far best video on Amortized Analysis. Thanks a ton❤️

[@NERDfirst]

You're welcome! Very happy to be of help =)

[@tessacarstairs5998]

thank you! You teach wayyyyy better than my professors do!

[@NERDfirst]

You're welcome! Very happy to be of help =)

[@tessacarstairs5998]

@@NERDfirst you are so sweet!!!!

[@ahmadfrhn97]

i find it amazing when you can explain to me better compared to my lecturer in a 2 hour lecture. and heck most of the example came from your video 🤣 #keepUpTheGoodWork!

[@NERDfirst]

Hello and thank you very much for your comment! The example given is the most classic example, that's why you'll see it common to a lot of explanations on this topic!

[@didar380]

This saved me a lot of time. Appreciated!

[@NERDfirst]

Hello and thank you for your comment! Happy to be of help =)

[@elijahsawyers8950]

Just subscribed because of this video...it's 100x better than my professor's method of explaining this concept. However, could you please explain how amortized analysis works for deleting elements in a dynamic array?

[@NERDfirst]

Hello and thank you for your comment! I'm afraid it's not something I've given much thought to so I don't have an answer for you. However, I found something online that may be of use: www.cs.cmu.edu/afs/cs/academic/class/15451-s15/LectureNotes/lecture06/growing-shrinking-table.txt

[@Twxwt]

This is the best video about Amortized Analysis! Thank you

[@NERDfirst]

Hello and thank you very much for your comment! Very happy to be of help =)

[@Kri38]

thank you for making this video. the pace of the video was perfect.

[@NERDfirst]

You're welcome! Very happy to be of help, and thank you for the feedback! Pacing is something I'm always very unsure about, so I'm glad to know ti worked well for you!

[@MinhLe-xk5rm]

Awesome video on amortized analysis! Thank you!

[@NERDfirst]

Welcome! Very happy to be of help =)

[@natsableyourself]

Wow, very well explained. Please, keep them coming!

[@NERDfirst]

Hello and thank you for your comment! New videos every week =)

[@ppydpc]

Nicely presented! Very clear and well thought-out.

[@NERDfirst]

Hello and thank you very much for your comment! Glad you liked the video =)

[@mikevollenweider3279]

Very clear and concise. Thank you!

[@NERDfirst]

You're welcome! Very happy to be of help =)

[@s7887177]

This video is so awesome... save me a bunch of time to study

[@NERDfirst]

Hello and thank you very much for your comment! Glad you liked the video =)

[@firaseljerdy1244]

Hello, great video! Just one thing. At minute 7:16, why did we inflate the numbers and forced an expansion? Could have we just done it with out the inflation? Thanks.

[@NERDfirst]

Hello and thank you for your comment! The inflation starts from 6:30 actually. The reason why we do that is to create a series of additions 1+2+4+8+... instead of having it start as 4. This helps us see the pattern more clearly later on, where the total cost is almost 2x the number of operations (7:23).

[@firaseljerdy1244]

@@NERDfirst yes sorry I put the time wrong. Okay so this just for demonstration purposes? If we leave it as it is, can we prove that its the double without the inflation? Thanks

[@NERDfirst]

Hello again! Personally I feel it is more convincing for a proof to start with an array of size one (ie. The "inflated" version as I have shown). Otherwise, you'll have to explain your arbitrary choice of starting array size, and you could be questioned about whether your proof holds true for smaller array sizes. The clearest proof shows that the _worst case time_ (ie. Even if we start with an array of size one), still gives us under 2x number of operations.

[@tech-talks-with-ali]

Thanks for your explanations about amortized analysis. It was helpful for me :)

[@NERDfirst]

You're welcome! Glad to be of help =)

[@christianwu8042]

Thank you so much! Extremely helpful video!

[@NERDfirst]

You're welcome! Very happy to be of help =)

[@mustafamohammadi5741]

Perfect explanation. Great Job

[@NERDfirst]

Hello and thank you very much for your comment! Glad you liked the video =)

[@lightstrike7466]

finally got that stuff :D my teacher failed explaining it for over a week now xD thx a lot m8!

[@NERDfirst]

You're welcome! Very happy to be of help =)

[@wentingyu6095]

Thank you so much. I finally know the difference between accounting and potential in real examples and know how to calculate them now (cry)

[@NERDfirst]

You're welcome! Very happy to be of help =)

[@seireen938]

Helped me a lot for my upcoming test! Thanks a lot!

[@NERDfirst]

You're welcome! All the best for your test =)

[@Ashmole3]

That was very clear. Thank you.

[@NERDfirst]

You're welcome! Very happy to be of help =)

[@TonyPepperoni27]

Great explanation! Thank you

[@NERDfirst]

You're welcome! Glad to be of help =)

[@bpglogic]

Explained it so well. Kudos to you and subscribed:)

[@NERDfirst]

You're welcome! Very happy to be of help =)

[@forrest-forrest]

Wow this is great. Thank you so much!

[@NERDfirst]

You're welcome! Very happy to be of help =)

[@astaragmohapatra9]

This was really helpful, thank you

[@NERDfirst]

You're welcome! Very happy to be of help =)

[@mahditalebi1770]

great explanation! good job sir. very helpful

[@NERDfirst]

Hello and thank you for your comment! Very happy to be of help =)

[@hakan6449]

This helped a lot. Thanks! Initially I didn't want to click on this video because the thumbnail looked bad though. So if you made it better I think it would get more views.

[@NERDfirst]

Hello and thank you very much for your comment! I don't usually give a lot of thought to thumbnails, so this is valuable feedback - Could you elaborate more on what was off-putting about it? I'll see what I can do to make it better!

[@CasanovaKingpin]

awesome video man ...very well explained each and every step .

[@NERDfirst]

Hello and thank you very much for your comment! Glad you liked the video!

[@高板丽奈单推人]

Bro you are a legend. 😭

[@NERDfirst]

Hello and thank you for your comment! Well, I'm glad you liked the video =)

[@hedic414]

Thank you for this. So helpful!

[@NERDfirst]

You're welcome! Very happy to be of help =)

[@minh-trungtang7769]

omg this deserves a subscribe thanks bro

[@NERDfirst]

You're welcome! Glad to be of help =)

[@samarthsudarshan4868]

Great content!!

[@NERDfirst]

Thank you very much! Glad you liked the video =)

[@sonalipundpal]

The explanation was good...It really helped me

[@NERDfirst]

That's great to hear! Very happy to be of help :)

[@rakoonberry7879]

Very helpful video. Thanks :)

[@NERDfirst]

You're welcome! Very happy to be of help =)

[@Daniel-iy1ed]

Fantastic!!! Thank you so much

[@NERDfirst]

You're welcome! Very happy to be of help =)

[@ronthedon212]

sir, thank you very much. this is a great explanation and great intuition content

[@NERDfirst]

You're welcome! Very happy to be of help =)

[@faxmunke9763]

Thank you for the video!

[@NERDfirst]

You're welcome! Glad to be of help =)

[@nirajchowdhary7372]

Thank You buddy you explained it very well!!

[@NERDfirst]

You're welcome! Very happy to be of help =)

[@mc3749]

Thank you so much. this is super helpful.

[@NERDfirst]

You're welcome! Happy to be of help =)

[@satyadharkumarchintagunta3793]

Sir,you explanation is tooooooo good🙂🙂🙂

[@NERDfirst]

Hello and thank you for your comment! Glad you liked the video =)

[@hashankarunathilaka4229]

Great content. Thanks a lot. It helped me big time

[@NERDfirst]

Hello and thank you very much for your comment! Glad to be of help =)

[@williamTjS]

Amazing video, thank you

[@NERDfirst]

You're welcome! Happy to be of help =)

[@MrEyee2]

Why anyone would give this a thumbs-down is beyond me.

[@NERDfirst]

Hello and thank you for your comment! I wouldn't worry about that =) What's important is that people have found this useful!

[@Stuck.in.Matrix]

Great explanation.. thanks bro

[@NERDfirst]

You're welcome! Happy to be of help =)

[@UditPandyaIRZealot]

Simply Superb !

[@NERDfirst]

Thank you very much! Glad to be of help :)

[@fz8227]

Very clear! Recoommend

[@NERDfirst]

Thank you very much! Glad you liked the video =)

[@benjaminmathew9061]

Thank you! Question about accounting method - how do you decide how much to charge? I'm sure you're not randomly guessing or pulling numbers out of thin air. Is there a method to deciding costs?

[@benjaminmathew9061]

Same question regarding how you came up with the potential function

[@NERDfirst]

Hello and thank you for your comment! The way I see it, some amount of trial and error is unavoidable. A good gauge would be to consider how the expensive operations can be "divided into" a number of "cheaper" operations. Set up some numbers from there and try. If the number keeps increasing, consider assigning less to each operation. If the value dips below zero, then the cost must be increased. For deriving potential functions, it may be advantageous to first consider the aggregate method, which allows you to consider step-by-step costs which you can then "generalize".

[@abelhecker]

thanks, it was very helpful :)

[@NERDfirst]

You're welcome! Glad to be of help =)

[@shil331]

thanks man, very good explanation

[@NERDfirst]

You're welcome! Glad to be of help =)

[@dharmilshah4934]

It was a really great video and has given a great understanding for amortized analysis.... I just had one doubt, that why do we have 1 in (1+i) because 'i' is used for moving 'i' elements but likewise we are also inserting 'i' elements right?.. So shouldn't it be (i+i) ?

[@NERDfirst]

Hello and thank you for your comment! Don't forget, (1+i) is discussed at a time when we're talking about what's going on *step by step* , in other words, on a *per-operation basis* . At any point of time, we are inserting 1 item only. However, there are some cases in which inserting that 1 item causes a chain reaction in which _i_ additional things happen. In that case, the amount of work done *for that one step* is (1+i).

[@Tee_eej]

Great explanation! You are made to teach

[@NERDfirst]

Hello and thank you for your comment! Glad you found my work useful =)

[@vaibhavsingh1049]

At 6:49 , wouldn't adding item 3 also trigger an array expansion?

[@NERDfirst]

Hello and thank you for your comment! No, there will be no array expansion for the third item, as at that point, the array has a size of 4. After inserting "2", the now full array (of size 2), is transferred to an array double in size (size 4).

[@vaibhavsingh1049]

@@NERDfirst Thanks for replying so quick. I think I get it now.

[@NERDfirst]

You're welcome! Glad to be of help =)

[@dragonpig9842]

Great video! May I ask you what is a good way to come out with the potential function?

[@NERDfirst]

Hello and thank you for your comment! Unfortunately there is no "one rule" or method for doing that. You'll have to just get your head into the right space and reason it out. There's a good writeup here to start building that intuition: cs.stackexchange.com/questions/30543/what-is-the-intuition-behind-the-potential-function-in-amortized-analysis-of-som

[@dhananjaynaik6391]

Hey man. Thank you. It helped a lot.

[@NERDfirst]

You're welcome! Very happy to be of help =)

[@asefsgrd5573]

Great video ever!

[@NERDfirst]

Hello and thank you for your comment! Glad you liked the video =)

[@kishore4994]

Nicely covered

[@NERDfirst]

Hello and thank you for your comment! Glad you liked the video =)

[@blacklight8932]

13:56 You have defined this function but how? How do I define phi(h)?

[@NERDfirst]

Hello and thank you for your comment! As mentioned in the video, this is the challenging part. There is no single method that will reliably generate such a function for you. Some frameworks for reasoning about it do exist and I'll link it here, but ultimately your own experience and pattern recognition skills are required here. Further reading: cs.stackexchange.com/questions/30543/what-is-the-intuition-behind-the-potential-function-in-amortized-analysis-of-som

[@blacklight8932]

7:23 What exactly is the number of operations here? 63 < ? Isn't the total cost the number of operations?

[@NERDfirst]

Hello and thank you for your comment! The point is to think of this in the abstract! Whether the same algorithm runs for N=4 or N=1000000, the relationship holds. For that example, the total cost of expensive operations (ie. All the array expansions) is 63. There have been 32 insert operations on the array. Hence, the cost is always bounded by 2 × the number of insertion operations.

[@anonInDE]

With the accountant's method... I don't get why you assigned $3 per operation.... I mean what's to stop me from assigning $10, or $20 per operation, or even infinity and then I could use that same argument to argue that any operation amortized costs O(1) only! Where did I get these $3 from? I can't seem to grasp that... Can anybody explain that to me please?

[@NERDfirst]

Hello and thank you for your comment! The costs assigned are arbitrary, but there is a strategy to picking them. The general idea is that we want to _count_ the number of fundamental units of operation (which we usually assign as $1), and see how many of them take place on average "per step" over a data structure of size n. Of course you could give it $10 or $20, but: 1) In general, we are talking about worst case time complexity, so we want a tight bound. It's the same way saying bubble sort has a worst case time complexity of O(2^n) isn't _technically_ wrong (Big O notations only specify an upper bound), but saying this becomes meaningless because _tight_ upper bounds are more useful. 2) If the algorithm can't be amortized to O(1), using a large constant cost won't help you - You will get to a point where the $10 or even $100 or $1000 you assign won't be enough. Of course, infinity is another question altogether. If you use infinity the whole exercise becomes pointless because you'll never run out, so you can't do that.

[@christopherweeks89]

great video!

[@NERDfirst]

Hello and thank you for your comment! Glad you liked the video =)

[@chaochen511]

I like your shadow on the wall

[@NERDfirst]

Shadow likes you too!

[@amitmohanty2679]

Thank you for the amazing explanation. Just a doubt In Aggregate analysis isn't the cost of an expensive operation is 4 when 3 items instead of 4 items. This is due to the new array creation point is when we try to insert 3 item to the dynamic array. Correct me if I am wrong.

[@NERDfirst]

Hello and thank you for your comment! It depends on when you want to expand the array. In the example shown, we expand the array when it becomes full as the result of an insertion operation. You can of course choose to do this earlier.

[@amitmohanty2679]

@@NERDfirst Thank you.

[@moritzgoe]

Great Video! :)

[@NERDfirst]

Hello and thank you very much for your comment! Glad you liked the video =)

[@sadiahabib5506]

Wow better than teachers there in university. I wonder about people who disliked 🤔🤔

[@NERDfirst]

Hello and thank you very much for your comment! I wouldn't worry about dislikes, what's important is that the people who need my help get it :)

[@aswing2706]

Thank you brother

[@NERDfirst]

You're welcome! Glad to be of help =)

[@marcocaniglia3061]

Awesome video, wish my boring professor just showed us your video in class instead of wasting our time for 1.5hrs lol

[@NERDfirst]

Hello and thank you for your comment! Heh, it's not an easy topic to deliver on the go, so I can understand. Either way, glad to be of help =)

[@EibeMandel]

Perfect, thanks

[@NERDfirst]

You're welcome! Happy to be of help =)

[@jakobskovsndergard7912]

fantastic video: just a tiny comment. is the cost correct in the table with the aggregate stuff. I would expect the cost to be: 1,2,3,1,5,1,1,1,9,1,1,1,1,1,1,17……because we copy when we want to insert to a full table that has no more space, not when inserting to the last slot in the array.

[@NERDfirst]

Hello and thank you for your comment! An interesting thought, but it works out all the same, because the work kicks in at comparable points in time - The total amount of work done is exactly equal. I would say both strategies are equivalent, though round powers of two are nicer to look at =)

[@Samuel-wl4fw]

Great video

[@NERDfirst]

Hello and thank you for your comment! Glad to be of help =)

[@absence9443]

Quick n neat, do you have to guess the cost for accounting and function for the potential method?

[@NERDfirst]

Hello and thank you for your comment! I don't think you'll really ever need to blindly guess in the dark. If it helps, start with the aggregate method first to see a pattern. Of course, there's no single method that will always give you a perfect answer from the get go, so some experience and pattern recognition skills are required, but there are some frameworks for reasoning about this. Here's a pretty good writeup: cs.stackexchange.com/questions/30543/what-is-the-intuition-behind-the-potential-function-in-amortized-analysis-of-som

[@absence9443]

@@NERDfirst thank thee :)

[@mahwishch3883]

excellent work..keep it up (Y)

[@NERDfirst]

Thank you very much! Glad you liked the video =)

[@gopikrishnan7380]

Thank you sir.

[@NERDfirst]

You're welcome! Happy to be of help =)

[@milda1220]

GOOD JOB!

[@NERDfirst]

Thank you very much! Glad you liked the video =)

[@johndambrosio7410]

During the accounting method, what is the cost for creating the new, double in size, array?

[@NERDfirst]

Hello and thank you for your comment! Intuitively I'd say _creating_ the array is O(1) since that just involves setting aside a contiguous block of RAM (assuming availability). It's the _shifting_ of items from the old array into the new that takes O(n).

[@farruhhabibullaev5316]

It is cool bro. Thank you

[@NERDfirst]

You're welcome! Glad to be of help =)

[@AkashVerma-sq8eq]

Even if the number of cheap operations are NEARLY (and not equal to n) n times, is it correct to say it's total cost is of order O(n)?

[@NERDfirst]

Hello and thank you for your comment! To greatly oversimplify, the Big O Notation just indicates the fastest growing component. So usually when we see c*n + a (where c and a are constant numbers), we'll just represent it as O(n). For more on this topic, you may want to check out my playlist on asymptotic notations: kzbin.info/aero/PLJse9iV6Reqh5B_w9koGyT7nlYm92iITk

[@thepinkcodon]

I have a question, somebody please help! In the aggregate method, how exactly are there n number of operations? In this example, for the total cost in the aggregate method, it's a GP with sum = 2n-1. So, the total cost is of complexity O(n). But for calculating the average, why did you divide it by n? How is the number of operations = n? Also, what exactly do we mean by operations here?

[@NERDfirst]

Hello and thank you for your comment! The number of operations is n because there have been n item insertions into the array. The most sensible definition of "operation" is one unit of work, as in, one thing you can do to said data structure. Clearly this will vary depending on what problem you're trying to analyze. However, generally speaking, if you're analyzing a series of steps and want to find out the amortized time complexity, then you'd want to divide by the individual steps that make up the series of operations.

[@thepinkcodon]

@@NERDfirst Thank you for the explanation. :)

[@thanglai4880]

could you explain for me what is the mean of cost you use in aggregate method ? is it related to big o notation ? Again, many thanks for your videos.i really appreciate it

[@NERDfirst]

Hello and thank you for your comment! Cost "leads" us towards coming up with a conclusion for Big O time complexity, though when we're discussing "cost", we're not quite there yet. Think of cost as a count of the number of steps, as in 1 unit of cost is equivalent to one step.

[@parikshitrajpara5706]

good work

[@NERDfirst]

Hello and thank you for your comment! Glad to be of help =)