What is Amortized Time Complexity? - Dynamic Array

Подписаться 583 тыс.

Просмотров 127 тыс.

50% 1

Amortized time complexity analysis for an algorithm involves taking to total cost of operations in the algorithm over an extended period of time.
Amortized cost is useful when the cost of operations in an algorithm vary as per the state of the underlying data structure or time. In these cases, the average cost over an extended period of time is usually lesser than worst case operation cost.
We take the example of a dynamic array, in which the size of the array is doubled on overflow, and elements are inserted N times. We come to the conclusion that the overall time complexity should be O(N) amortized.
Link to code:
• What is Amortized Time...
References:
www.cs.cmu.edu/afs/cs/academic...
www.cs.cornell.edu/courses/cs3...
anh.cs.luc.edu/363/notes/06A_...
Time complexity explanation:
• What is Time Complexit...
Log explanation:
• Why does log(N) appear...

Опубликовано:

19 фев 2018

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 127

@jceddy1 4 года назад

@5:29 When you double the size of the array, I think this is language specific. If using C e.g. "int a[4];" which is constant time since it's just moving a pointer. If using java, its O(n) because the JVM specifies arrays are initialized "Each of the elements of the new array is initialized to the default initial value for the type of the array (§2.5.1)" This gave me a bit of confusion watching the video, so I think it's helpful to point out. Thanks for the explanation!

@gkcs 4 года назад

That's a good point :)

@jaswanthm9775 4 года назад

Thanks bro for clearing this as I was bit confused at this point

@derpnerpwerp 2 года назад

Came here to mention this. Although it's been a long while since I've done C/C++ but I think your example of "int a[4]" isn't really applicable since that is a fixed length array. This would require dynamic memory allocation so I believe that uses new/malloc. Regardless I don't think you can concern yourself with the time complexity of those operations at this level as they are beyond your control and actual time could vary significantly. I wonder if it is always the case that default initialization requires an individual cpu operation. Seems like a hardware memset would be doable. memcpy is also going to be optimized for the particular hardware you are using.

@RidhimaMusic27 5 месяцев назад

Where did 3 come from in this??

@charlesandrews8790 4 года назад

The best video I've seen on this concept! Thanks so much man and keep it up, your videos are a really valuable resource.

@dirtycrumbs 5 лет назад

ive been through 3-4 text book explanations of this and it's never settled. finally get it (!) thanks bud B-)

@nirajverma3515 6 лет назад

You sir a genius..Thank you so much for your data structures and algorithm playlist

@sanjeevjayasuryas5277 5 лет назад

You've come a long way from here man! It's like you're born for this. Keep up the good work.

@gkcs 5 лет назад

Thanks!

@divyasingh7211 6 лет назад

I am a big fan of yours aaj se!! The way you deliver!! It's so damn energizing and gets straight into the brain! Too good!! Thank you so much for this!

@gkcs 6 лет назад

Thanks Divya 😁

@bhagwatibhalotia7636 6 лет назад

Wow, this was VERY useful! I always believed that dynamic arrays took close to O(N^2) in practice too... But this is clearly not the case.. Thanks a ton for removing this misconception! - Akash Bhalotia

@gkcs 6 лет назад

Thanks Akash!

@deepanshu788 4 года назад

Gaurav, that was an informative video. Cleared all doubts I had relating to the topic.

@devanshmesson2777 2 года назад

Best video for Amortized Time Complexity explanation! Thanks!

@allanhenriques2694 3 года назад

moreover, if you want to calculate the amortized for adding a single element, you can take the cost for adding n elements which is O(n), and divide it by n, resulting in O(1)

@jairogarciga3092 Год назад

Really good stuff, thank you for your work!

@parvezmulla3324 6 лет назад

Useful! Thanks for making videos.

@gkcs 6 лет назад

Thanks Parvez!

@q1chen 3 года назад

Perfect explanation, better than my lecturer. thank you

@ahnafsadat4291 10 месяцев назад

Your explanation was much better than US University Professors.

@sathya3596 4 года назад

never understood in clg! tnkx for the explanation bruh!!

@vvsganeshchandra6120 6 лет назад

thank you sir...very nice explanation

@Marina-pe1gx 4 года назад

thank you so so much for the video. At no point do we do 3*(2N)+1, because 3*size+1 has, as size, the size of the preexistant array. 2N is the maximum we reach. Shouldn't what you write at 8:31 stop at N?

@vishwajeetparadkar1420 4 года назад

Great video brother.

@palakmantry 3 года назад

excellent explanation!

@workflop4117 4 года назад

Thank you so much for this explanation really clear, you have what i can see next?

@SamareshMaity231 2 года назад

Thank you @Gaurav, very less discussed topic in internet, I got a doubt that after pushing elements in vector, the address of first element was changing. I tried searching on google, but didn't found any helpful solution, you cleared my doubt. Thank you

@mohammadsaleh9316 5 лет назад

Thanks a lot. I was trying to understand the concept of amortized analysis for the past two weeks but failed. This one single video made everything clear to me!

@10_bhaveshbathija31 Год назад

Thanks for the explanation. It helped me alot.

@rishonfernandes7976 3 года назад

This was pretty good!

@amankhunt3620 4 года назад

Amortized cost is used to find cost of an operation in context of sequence of operations , rather than analyzing single worst case operation. Three approaches - a) Aggregate method b) Bankers c) Physicist method. Correction:- Amortized cost of each insertion in dynamic array( considering doubling every time when its full) should be O(1) and not O(n). O(n) comes when we are increasing/adding array size by constant number.

@169mayan 4 года назад

you need to be clear about insert and append, both are not the same. Insertion will take 0(N) as we have to shift elements. while appending is O(1) just adding to the last index. ofc when we don't have to resize our array

@priyankamanna4550 3 года назад

Good one !!!!! Ur teaching skill and communication skill is lit🔥😀

@gkcs 3 года назад

Thank you 😁

@anilchaudhry804 4 года назад

Hi gaurav, How do you implement reverse dns using tries?? Please make a video on that

@devilscardistro6557 4 года назад

if we want to enter even one element after N elements we double the size fine. but how can complexity be 2*n . creating an array of 2*size will take constant time . then copying the array will take size time. then the elements inserted let say k. so time becomes size+k ??

@chandreshmaurya8102 4 года назад

I'm wondering on the calculation of worst case O(n^2) complexity. Why every insertion costs c= 3*size of the array everytime you double the array? You got c based on doubling array when you hit the memory. Now for every insertion you don't git that limit. Or to rectify the cals, worst case will occur for every L+1, 2L+1, 4L+1,...,2^kL+1 element only (L=size). which on simplifying gives k= log((N-1)/L) which is very small. For other N-k elements , insertion is O(1).

@shubhankaringale278 2 года назад

Thanks... it helped me a lot

@sahilanand30 2 года назад

Nicely explained

@cyberspace23 5 лет назад

Nice explanation, but major problem with audio.

@gkcs 5 лет назад

Thanks Deep! The audio has improved a lot since then. You could check out the newer videos 😋

@vismarkjuarez8102 3 года назад

Thank God for subtitles.

@klotzak1987 4 года назад

why are you considering the creation of a new empty array of size N in time complexity calculation with value of O(N). E.g. when size is 8 and you want to enter 9th element then size of array is doubled, in this calculation you considered the time complexity for 9th insertion as 16 + 8 + 1. Why the 16? If you don't consider that, i.e. creation of an empty array as O(1) operation then also the final calculation remains same. Isn't it?

@devilscardistro6557 4 года назад

@@Pctech4uproductions if we want to enter even one element after N elements we double the size fine. but how can complexity be 2*n . creating an array of 2*size will take constant time . then copying the array will take size time. then the elements inserted let say k. so time becomes size+k ??

@haiwenwang5587 5 лет назад

Excellent explanation, sir! Neat and easy to understand, except for the accent. But I have to admit, you are an excellent teacher

@gkcs 5 лет назад

Thanks Haiwen! My accent would be really hard to change, but I'll try and be as clear as possible 😁

@ninjaweave8779 5 лет назад

@@gkcs Found your accent perfectly clear and easy to understand from a UK native, great explanation really easy to understand much better than any of my lecturers thank you very much :)

@gkcs 5 лет назад

@@ninjaweave8779 Thank you!

@awalehmohamed6958 3 года назад

@@gkcs You accent is fine man, dont worry. Great english

@gamingdemons3746 5 лет назад

keep it up dude...

@gkcs 5 лет назад

Thanks!

@ankanderia4999 Год назад

1+2+4+8+...+2N = 2^N -1 not (2*N - 1). But yeah I understand that if the array grows like that then time complexity will reduce. then will the space complexity become more ?

@abhinav788 Год назад

This was nice explaination. Could you please tell some book which I can refer to for learning this concept? It would be highly appreciated if you reply. Thank you !

@GEhehloopf 3 года назад

Could you explain how to get 2N*2-1 from the geometric formula in 9:41?

@techinternals 3 года назад

Sum of geometric series : S = (a * r^n - 1) / (r-1) For that question, n = logbase2(2N) + 1 and a = 1 , r = 2 S comes out to be (2N * 2 - 1)

@vinaynagalgaonkar2214 6 лет назад

Sir can please make video on Dirichlet Convolution and Treaps .

@anaybaid Год назад

LOVE YOU MY MAN!!

@gkcs Год назад

Thank you!

@abhinavtyagi1657 3 года назад

In the worst case, the number of elements that are going to be inserted should be around 2N - 1 and not 2N ????????? Can anyone help me ?

@saketshrivastava7169 4 года назад

kaha se laate ho itna confidence

@skalippanbalippan6972 3 года назад

Why doubling the size of the array is taking 2 and not 1?

@deepaknegi7589 4 года назад

Thanks, Sir, but I have one doubt when we reach the end of the array and create a new array of doubled size, so when we create an array of doubled size will it require 2*n time complexity?? The copying of old elements to the new array will definitely take old size(n) time complexity, but the (2*n) time complexity part of doubling the array, I couldn't understand.

@vansh2k6 3 года назад

I also have same doubt. Do you know the answer now? If yes, can you please put it as a reply to my comment

@deepaknegi7589 3 года назад

@@vansh2k6 No, I haven't got the answer till now, I am still unable to understand this

@Omar-ic3wc 3 года назад

Yea it will require 2N cause you double the size of the the array(you create a new array of double size of the previous array) and when you copy all the past elements you need N time as well, so will be 3*sizeof N, hope it helps you brother.

@shashwatsharma8799 3 года назад

From the first second itself I understood what is Amortization means. So, basically it is an average, so to say. Correct me if I am wrong. Beginner at all these stuff

@aswinosbalaji4224 6 лет назад

hai the video is great but I have a doubt atlast shouldn't we divide it by N so the answer is a constant 13. cause you said in the intro it is an average for extended period of time. Another site has explained Ed the same example with result of O(1).

@gkcs 6 лет назад

We could do that too. Total complexity is O(N). That gives us an amortized complexity of O(1).

@krypto7264 5 лет назад

constant 13 or 3??

@harshsaxena1999it 5 лет назад

what they mean to say is that each operation would be of O(1) so n operations would be of O(n)

@hobbies.central 6 лет назад

Too good... It is very helpful.. but does arraylist double the size or increase it by 50%?

@gkcs 6 лет назад

I think it doubles the size. Will have to revisit the documentation to be sure :-)

@sayandey1478 5 лет назад

how doubling the size consumes time? Rather it should be a space issue and should affect the space complexity, na?

@gkcs 5 лет назад

Check out how the operating system allocates space to a program.

@prashanthnvs3719 5 лет назад

@@gkcs so its space complexity but not time complexity

@shishirjha 5 лет назад

Exactly! I have looked in some places online and reputed sites. There i found that amortized cost for insertion in dynamic array is constant time not O(n). Rather, the worst case time for insertion is O(n) which Gaurav has pointed to be O(n^2) .

@devilscardistro6557 4 года назад

@@shishirjha if we want to enter even one element after N elements we double the size fine. but how can complexity be 2*n . creating an array of 2*size will take constant time . then copying the array will take size time. then the elements inserted let say k. so time becomes size+k ??

@tejasbhawre5301 2 года назад

where u r cpopying elements of new elements??

@deeproy7292 6 лет назад

thank you

@deeproy7292 6 лет назад

an awesome explanation but according to me , time complexity for such an algorithm must be constant. Do tell me after considering this example in the link : www.geeksforgeeks.org/analysis-algorithm-set-5-amortized-analysis-introduction/ Thank you

@lukekim825 4 года назад

can somebody tell me why we are creating a new array with x2 the original array length? Why dont we triple it or simply make a new array that is only 1 size bigger? is there something special about doubling or is that just how it is?

@gkcs 4 года назад

Did you understand the analysis in the video?

@lukekim825 4 года назад

@@gkcs Yea I understand why adding elements in a dynamic array can look like O(n^2) but thru amortized analysis, the problem is actually O(n). My question is when we are adding another element in a dynamic array that is filled, do we always make an empty array that is double the size of the original array? Sorry if this question is too petty

@jaydenurch271 4 года назад

@@lukekim825 I know this is 8 months old, but anyways. The doubling is arbitrary and based on the implementation. You could increase it by 1, increase it by 50%, double it, triple it, it's up to the specific implementation. However, there is a trade-off to each of these. A lower increase each time would result in less memory being used, but needs to increase in size more often. A larger increase size is the opposite, it needs to increase less often, but uses more memory.

@nihar1213 5 лет назад

khub bhalo!

@pushkarajsarnobat8884 4 года назад

What if I wish to resize the array by adding 2 and not by doubling the array. Meaning every time the array is full I wish to increase the size of the array by 2 and not double the array size by existing size. what will be the amortized cost of this?

@gkcs 4 года назад

Think about it and let me know. 😁 It's not going to fare well, btw.

@pushkarajsarnobat8884 4 года назад

@@gkcs Trust me i have spent like more than 2 days thinking over it, dint get any solution . It would be great if you could help me out in this :D

@gkcs 4 года назад

@@pushkarajsarnobat8884 When you assign a new array, the time required is proportional to it's size. If for every two elements, we need to assign an array of it's size, it's a problem. Start with size 2. Insert. Insert. Now make the size 4. Insert insert. Now make the size 6. On every 3 inserts, you are assigning a new array. Cost for n elements will be 2+4+6+...+n. That's O(n^2).

@pushkarajsarnobat8884 4 года назад

@@gkcs I'm sorry I'm not following you on this. My question is I want to try to increase the size with every insert by just two over the previous size. What is the amortized cost per insertion in this case? Meaning How much should be the cost of inserting a new element and what should be the cost of copying the existing elements into a new array

@gkcs 4 года назад

@@pushkarajsarnobat8884 You need to watch the video a few more times.

@vijayanks1714 2 года назад

Amortized analysis means instead of looking in the worst case all the time which is actually impractical you should have deep understanding of how the algorithm working and you can bring down from order n square I mean though the analysis form the poor analysis of order n square to correct analysis of order n

@subarnasarkar499 4 года назад

Very good explanation but where is the code??

@gkcs 4 года назад

github.com/gkcs/Competitive-Programming/blob/master/src/main/java/main/java/videos/DynamicArrayMain.java You can check the video description for the code explanation link 🙂

@Airman.programer 10 месяцев назад

Great video bro but the audio quality was not that great

@rakeshsingh-hj4ly 6 лет назад

Isn't amortized insertion runtime is O(1)?

@gkcs 6 лет назад

Yup. Total time is O(N), which makes the amortized insertion time O(1).

@prakashpanda2702 4 года назад

your sound quality of this video is not well,its difficult to understand

@zhanminglau6780 5 лет назад

At 9.40 , the sum of (1+2+4+...+2N) according to the video is 2*2N - 1 , but if calculated with the formula of geometric progression , shouldnt it be Sn=a(r^n-1)/r-1, and assuming the worst case , the number we gonna reach is 2N and the ratio should be 2 , so it will be (Sum of 1+2+...+2N)=1((2^2N)-1)/2-1 , which is 2^2N -1 not 2*2N-1 . Correct me if i am wrong , the video is great btw.

@nityachandra3472 5 лет назад

here no. of terms is not 2N. It's log2N(base 2). Hence, it's correct.

@hippo50410 5 лет назад

Good explanation. Bad audio.

@rahulmalawadkar1936 6 лет назад

Cool hairstyle!!

@gkcs 6 лет назад

Hahaha, thanks Rahul :-p

@ruksaranjum9452 5 лет назад

Wht is d time complexity of insertion and deletion in an array

@gkcs 5 лет назад

Infinity :)

@ruksaranjum9452 5 лет назад

@@gkcs ty☺

@achintyasarkar9757 6 лет назад

sir isnt the sum of gp (2^2N)-1

@achintyasarkar9757 6 лет назад

I mean if sum of gp given as (1 2 4 8 16 ....2N) is a((r^n)-1)/r-1 where a=1 and n=2N and r=2 then shouldnt it be (2^2N)-1 . By the way great work and really appreciate the enthusiasm and simplicity of your work

@deeproy7292 6 лет назад

how n = 2N

@nisargshah29 5 лет назад

n is log 2N base 2

@nisargshah29 5 лет назад

So It Should be 2N -1 ,how did it come 4N-1 I didnt understand.

@Arlinhajdaringagjila 5 лет назад

Sn = 2^(n-1) => n = log4N after the sum is 2N = 2^(n-1) it multiplies the right side so it is now 4N = 2^n and => n = log 4N. So 3(2^(log4N-1))-1 => based on logarithm formulas a ^ log a x = x (where a in the exponent is the base of the logarithm) so we can get the result 3(4N-1)-1 = 12N - 3 - 1 = 12N - 4 => O(12N) or O(N).

@prashanthnvs3719 5 лет назад

How can the cost be 1 or (2*n + n)? How are we getting the value '2*n' is it the cost to create the array?

@gkcs 5 лет назад

Watch the video again.

@devilscardistro6557 4 года назад

@@gkcs if we want to enter even one element after N elements we double the size fine. but how can complexity be 2*n . creating an array of 2*size will take constant time . then copying the array will take size time. then the elements inserted let say k. so time becomes size+k ??

@ramasivasubrahmanyampedire8660 4 года назад

Gurav sen . Why can't you type... You went through a wrong approach

@pranjal1275 6 лет назад

Can anybody tell me , how to be good in time and space complexity??

@abhishekrajan8208 6 лет назад

Please go through first 4 chapters of the book- "Introduction to Algorithms by CLRS" and practice the problems as well.

@vikrantdhawan4062 5 лет назад

my ans is 2N - 1 not (2N * 2) - 1 plz clear my dought ----------------------------------------------------------------------------------------- gp = a(r^n - 1) / (r - 1) 1+2+4+8+......+2N = 1(2^log(2N) - 1)/(2 - 1) = 2N - 1 plz explain how 1+2+4+8+......+2N = (2N * 2) - 1 derived

@akshaymathur2225 5 лет назад

This analysis is wrong, insertion in dynamic array is amortized constant time. Look here - www.quora.com/In-programming-languages-where-an-array-grows-dynamically-in-size-it-is-not-a-concern-because-it-is-O-n-time-complexity

@gkcs 5 лет назад

Isn't that exactly what is mentioned in the video? For n insertions, O(n) time. That gives an *amortized* complexity of O(1) => constant time. www.google.com/search?q=amortized+meaning&oq=amortized+meaning&aqs=chrome..69i57j0l5.2356j0j7&sourceid=chrome&ie=UTF-8