What is Amortized Time Complexity? – Dynamic Array



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:

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/

45 thoughts on “What is Amortized Time Complexity? – Dynamic Array”

  1. @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!

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

    Reply
  3. 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?

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

    Reply
  5. 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?

    Reply
  6. 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.

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

    Reply
  8. 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?

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

    Reply
  10. 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

    Reply
  11. 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

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

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

    Reply
  14. 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.

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

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

    Reply
  17. 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!

    Reply
  18. 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

    Reply

Leave a Comment