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

Question

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

Answer 1

The cost of adding one item at the end of the array of size n can be as large as O(n), but usually is much faster. That's why we use the term "amortized time". The work you did to add item #512 pays back for items 513 to 1023. It is "amortized".

The amortized cost per items is O(1), since the cost of adding n items individually is O(n).

There are various reasons why you have to be carefully with amortized cost: If you have a real time system where taking O(n) to add a single item in rare cases is not acceptable. For example, a system controlling the brakes of your car that has an amortized cost of 0.001 seconds for using the brakes once, but every 10,000 times takes 10 seconds is going to kill you.

There's also a difference between k individual operations, and combining k operations. If you have a sorted array of n items, and add a random item, keeping the array sorted, that takes O(n). However, if you want to add k items all in one go, keeping the array sorted, that takes O (n + k log k) (by sorting the k items first, then inserting them in one go). It is quite often that doing k operations can be done faster than doing one operation k times.