1
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ In a sequence of operations, effort~cost of expensive operations gets amortised in making others inexpensive. $\endgroup$
    – greybeard
    Mar 28, 2020 at 7:14
  • $\begingroup$ 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 $\endgroup$ Mar 28, 2020 at 7:39
  • $\begingroup$ 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? $\endgroup$
    – gnasher729
    Mar 28, 2020 at 7:49
  • $\begingroup$ I meant sequentially appending to the array. $\endgroup$ Mar 28, 2020 at 8:09

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you, this clears most of my doubts. $\endgroup$ Mar 28, 2020 at 8:08
  • $\begingroup$ But the only reason it " exactly pays back" for items 513 to 1023 is because we are dropping the constant "2" in O(2X) in my above explanation right? I mean, if we're talking about work done and not complexity, the average work done for every insert is actually going to be 2*c where c is the work it takes to do an easy insert. So in reality, it "pays back double" if we are looking at actual operations taken and not just at algorithmic complexity. Am I correct to think that it "pays back double"? @gnasher729 $\endgroup$ Mar 28, 2020 at 8:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.