# Can someone let me know if my understanding of amortized run time in a dynamic array list is correct?

Am I right in my understanding for amortized time for insertion in a dynamic array list? (dynamic means create a copy double its size and copy existing elements to new one WHEN we reach the current size limit). Please validate my explanation/understanding.

If we insert X elements into an array of initial size 0, it will perform the double/copy operation only at insertion number 1,2,4,8,16,..,X where each operation costs a function of X f1(X), f2(X), etc.

all other insertion operations like 3,5,6,7,9,10,11, etc is O(1).

the function of X which I mentioned above is because f1(X) + f2(X) +..+ fi(X) = 2X. where i is the number of double/copy insertions.

Hence, total execution time is O(2X+j.O(1)) where j is the number of easy operations. (3,5,6,7, etc) THIS is the part I want to verify if my understanding is right or not

therefore, total time is O(2X) = O(X)

but since we are looking for the time of only inserting one element, it is O(X) / X = O(1)

hence amortized time is O(1)

Last question: why is it called amortized? Where did I amortize anything?

Thank you!!

• In a sequence of operations, effort~cost of expensive operations gets amortised in making others inexpensive. Mar 28, 2020 at 7:14
• Where in my above proof/explanation am I amortizing expensive operations though? All I'm doing is disregarding the j.O(1) term because 2X is leading and we can disregard constant terms. I don't see where I am amortizing anything. 🧐@greybeard Mar 28, 2020 at 7:39
• Do you mean insert into an array or append at the end of an array? If you have 1000 array elements, how would you insert an element at index 507? Mar 28, 2020 at 7:49
• I meant sequentially appending to the array. Mar 28, 2020 at 8:09