hi friends welcome to my channel so this is the first topic of advanced data structures playlist amortized analysis or amortized time complexity so you would have already heard about asymptotic time complexity and how it is used to calculate the time complexity of different operations and in that you would have also heard about about big o notation the theta notation and all that so in this video we are going to talk about why uh amortized analysis or amortized time complexity computation is more important than asymptotic time complexity computation in some cases and i'll also give you a very simple explanation with the help of an example then we will talk about a very important feature of amortized analysis and i'll finally end this video with the help of an example of augmented stack and how amortized analysis is helpful when we are doing time complexity computation for augmented stack so first of all i have written over here if there are a series of operations where the cost of a single operation is very large so let us consider a data structure it can be any data structure so in that many operations are performed right there are many operations but there is this one single operation right our time complexity of this operation is very large or the cost of this operation is very large while the rest of the operations while the rest of the operations the cost of these rest of the operations is less so in such case the worst case the worst case running asymptotic time complexity may not give us a tighter bound now what this means is that in such cases what we actually do in case of asymptotic time complexity computation is that we find out the uh operation with the worst case time complexity and then we multiply it with the number of operations and this is how we get the time complexity for the total number of operations right this is how we do it but in such cases this is not a useful method so now let us discuss a real life example where amortized analysis is a better option than asymptotic analysis suppose there is a shop in which there are 500 items okay and the cost of each of these item is rupees one right each of these items costing rupees one right and there is another item in the shop you can call it the 501 item right and the cost of this item is very large it the cost of this item is rupees 500 okay so in total there are 501 items in the shop okay suppose i want to buy all these 501 items from this shop okay and i don't know how much money should i take with myself in the shop in order to buy all these 501 items so i asked my friend asim and aman to tell me that how much money should i take with myself in the shop so that i can buy all these 501 items so when i ask asim as he is a very conservative guy and he always wants to be on the safer side so what he tells me is that the maximum price of any item in the shop is rupees 500 okay this is the item with the maximum price so you should take 500 the maximum price of any item in the shop into the number of items in the shop into the number of items in the shop that is 501 right so he so he's asking me to approximately take 2 lakh 50 000 rupees when i visit this shop to buy all the 501 items okay and now there is another friend of mine that is aman he makes his own calculation and he says okay there are 500 items with rupees 1 each 500 into 1 plus there is one single item whose cost is 500 okay one item whose cost is 500 so you take 1000 rupees with you in the shop so he tells me to take thousand rupees with me in the shop so that i can buy all these 501 items so now whom should i listen to should i listen to asim or should i listen to aman of course i should listen to aman why because amman is doing a better analysis of the cost than asim right asim over here is just focusing on the item with the maximum price and on the basis of that he is multiplying it with the total number of items and he's doing his calculation right so he's kind of doing a worst case analysis right whereas aman over here is giving a much accurate or a better analysis than asim so i would definitely go with aman so if you have not noticed until now asim over here is the asymptotic analysis right asim over here is the asymptotic time complexity computation or the asymptotic analysis whereas aman is the amortized analysis right aman is the amortized analysis right so what asan is doing is an asymptotic analysis whereas aman believes in amortized analysis that is why he is giving us a more accurate analysis in such a case where in the shop just one single item has a very large price as compared to the rest of the items which have a lower price right so in such a case amman's analysis or the amortized analysis is a better option than asim's analysis or the asymptotic analysis now let us look at a very important feature of uh amortized analysis which is that in amortized analysis your average or worst case measure is not input dependent so what this means is that uh as you would have seen in case of like quick sort we say that the asymptotic worst case time complexity when the input is sorted we say it is big o of n square right so this when the input is sorted all these things that are input dependent they are not really important in case of amortized analysis let us look at augmented stack now first of all let me tell you what is augmented stack we will learn augmented data structures later on in this playlist but you might already be knowing the normal stack which has basically two operations uh the first one is push the time complexity of which is order of one and pop the time complexity of which is again order of one right so now let us consider another operation in this augmented stack which is multi-pop of k where k is the number of elements that we want to pop out at a single time out of this stack right and this multi-pop of k is actually defined something like this that it returns a false if k is greater than n of course when i'm i want to pop out the number of elements from the stack that are greater than the number of elements already present in the stack that's not possible so that is when it will return false and it will return true otherwise so this is my multi-pop of k now uh you can also consider the pop operation as multi pop of one right easy to understand okay so now uh what can be the worst case time complexity of multi-pop of k we found out the time complexity of push and pop what about the time complexity of multipop of k of course if uh we are asked to find out if we are asked to perform the operation multipop of k where k is equal to equal to n in this case the time complexity of multipop of k will be order of n right so now if suppose we want to do the time complexity analysis of this data structure which is augmented stack what we will do is that let us name this as time complexity analysis 1. we will see okay the operation with the worst case time complexity uh the time complexity of that operation is order of n and suppose uh we are doing it for n operations right so the time complexity for these n operations will be uh order of n into the number of operations that is n so the time complexity for these n operations will be order of n square right uh so this is how we are going to do it uh but there is a catch in this so we found out okay the time complexity should be order of n square but just consider one thing that uh suppose there were three two six nine suppose these were the elements in our stack in our augmented stack and again we tried to do the time complexity analysis and the first operation that we perform is multi-pop of n right so now as already mentioned the time complexity of this is order of n then the second operation that we perform is multi-pop of n is this possible no this is not possible because when we performed multiple of n what we actually did was we popped out all the elements so in the next step or the next operation again it is not possible to perform this this operation multipop of n with a time complexity of order of n so again to perform multi-pop of n actually what we need to do we need to push in those number of elements again right so i don't remember the elements but uh we need to push in the elements back so for that what we need to do for the next n operations till the n plus 1 operation we need to perform just push if we need to perform this multipop of n again over here right we just need to perform push and as you know the time complexity of push is always order of 1 so what we did over here now again if we do the time complexity analysis let's call this time complexity analysis 2 actually our total time complexity for all these n plus 1 operations the total time complexity is basically uh order of n this was for our first operation right plus order of 1 how many times this is n times so this is basically order of n plus order of n or you can call it order of n but here we found out that the time complexity analysis was order of n square whereas here we found out that it was order of n so this was basically our asymptotic analysis or the worst case time complexity analysis because here we considered okay the uh time complexity of the worst case operation or the cooperation with the worst case time complexity that is multiple of n is order of n so we were multiplied by the number of operations and we got order of n square but here when we did the actual calculation and when we understood that it is really not possible to do that worst case operation for a longer duration and that is when we got the uh time complexity for n number of operations again here it is for n operations right so the interesting thing over here is that uh for a single operation the time complexity of our augmented stack is order of n that is for n operations what is the time complexity divided by n the it remains as order of one so there is no change in our time complexity of our augmented stack even when we add this multipop k operation so this is these are the cases where amortized time complexity analysis is useful and it fulfills the property of amortized analysis where your average or worst case input does not depend on the average or worst case measure does not depend on the input so even what does this means is that how much ever elements were present in the stack one element of 1000 elements the time complexity will remain order of one itself for a single operation if we do the uh amortized analysis that's all for this video in the next video we will see the first method of amortized analysis which is the aggregate method