Java: ArrayList add() and remove() performance, implementation?

Question

I have read somewhere that ArrayList's add() and remove() operations run in "amortized constant" time. What does this mean exactly?

In the implementation of add(item) I can see that it ArrayList uses an array buffer, which is at most 3/2 of the list't size, and if it is full, System.arraycopy() is called, which should execute in O(n), not O(1) time. Is it then that System.arraycopy attempts to do something smarter than copying elements one by one into newly created array, since the time is actually O(1)?

---

Conclusion: add(item) runs in amortized constant time, but add(item, index) and remove(index) don't, they run in linear time (as explained in answers).

Answer 1

I have read somewhere that ArrayList's add() and remove() operations run in "amortized constant" time.

I don't think that is true for remove() except under unusual conditions.

• A remove(Object) call for a random element on average has to call equals on half of entries in the list, and then copy the references for the other half.

• A remove(int) call for a random element on average has to copy the references for half of the elements.

The only cases where remove(...) is going to be O(1) on average (e.g. amortized) is when you are using remove(int) to remove elements some constant offset from the end of the list.

Answer 2

"Amortized" roughly means "averaged across the entire runtime". Yes, an array-copy will be O(n). But that only happens when the list is full, which happens 1 in n times.

Answer 3

Amortised time explained in simple terms:

If you do an operation say a million times, you don't really care about the worst-case or the best-case of that operation - what you care about is how much time is taken in total when you repeat the operation a million times.

So it doesn't matter if the operation is very slow once in a while, as long as "once in a while" is rare enough for the slowness to be diluted away. Essentially amortised time means "average time taken per operation, if you do many operations". Amortised time doesn't have to be constant; you can have linear and logarithmic amortised time or whatever else.

Let's take mats' example of a dynamic array, to which you repeatedly add new items. Normally adding an item takes constant time (that is, O(1)). But each time the array is full, you allocate twice as much space, copy your data into the new region, and free the old space. Assuming allocates and frees run in constant time, this enlargement process takes O(n) time where n is the current size of the array.

So each time you enlarge, you take about twice as much time as the last enlarge. But you've also waited twice as long before doing it! The cost of each enlargement can thus be "spread out" among the insertions. This means that in the long term, the total time taken for adding m items to the array is O(m), and so the amortised time (i.e. time per insertion) is O(1).

Answer 4

I think that amortized constant time just means that it pretty much constant time if you do tons of operations. So in one test a million items to the list, then in another test add two million items to the list. The latter should be about ~2 times slower than the former, therefore, amortized constant time.

Answer 5

Amortized constant time is different than constant time.

Basically amortized O(1) means that over n operations, the average run time for any operation is O(1).

For array lists, this works something like:

(O(1) insert + O(1) insert + ... + O(n) array copy) / n operations = O(1)

Answer 6

An indepth description of the meaning of Amortized Constant in thread Constant Amortized Time