# What is Amortized Time Complexity? – Dynamic Array

45
3

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.

References:

Time complexity explanation:

Log explanation:

Nguồn: https://tvku21.com/

Xem thêm bài viết khác: https://tvku21.com/tong-hop/

1. @5:29 When you double the size of the array, I think this is language specific.
If using C e.g. "int a;" 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!

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

3. Vishwajeet Paradkar

Great video brother.

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?

5. Chandresh Maurya

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).

6. Pushkaraj Sarnobat

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?

7. Saket Shrivastava

kaha se laate ho itna confidence

8. Very good explanation but where is the code??

9. 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.

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

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

12. 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 ??

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

14. shreejit ray chaudhury

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?

15. 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?

16. Sanjeev JayaSurya S

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

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

19. This analysis is wrong, insertion in dynamic array is amortized constant time. Look here – https://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

20. 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

21. 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?

22. 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! <3

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

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

25. keep it up dude…

26. 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.

27. Please make videos in hindi

28. Deep Mandalaywala

Nice explanation, but major problem with audio.

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

30. khub bhalo!

31. vvs ganesh chandra

thank you sir…very nice explanation

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

33. 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).

34. thank you

35. 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!

36. Thank you! Finally a simple explanation of things. Well explained

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

38. Vinay Nagalgaonkar

Sir can please make video on Dirichlet Convolution and Treaps .

39. Sir can you make video on Tree path query and heavy light decomposition

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

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

42. Rahul malawadkar

Cool hairstyle!!

43. Bhagwati Bhalotia

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

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

45. Useful! Thanks for making videos.