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