# 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. – greybeard Mar 28 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 – gimmeshelter Mar 28 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? – gnasher729 Mar 28 at 7:49
• I meant sequentially appending to the array. – gimmeshelter Mar 28 at 8:09