Why is appending to a dynamically growing list constant time even though some individual appends copy the whole array?
Because most of the appends are cheap and the expensive ones are rare, and when you average over a whole sequence the expensive ones do not dominate.
class GrowableList:
def __init__(self):
self._items = []
self._size = 0
def append(self, value):
self._items.append(value)
self._size += 1
return self
So here is what happens. The list keeps some room spare at the end. Most of the time there is room, so the append puts the new item there and finishes straight away. That append does one step of work, and it is O of 1.
Once in a while the spare room runs out. Then the list takes a block that is about one and a half times as big, copies everything across, and carries on. That append does n steps of work, and it is O of n.
Now here is the part that makes the total work cheap. The copying happens less and less often as the list grows, because each new block is bigger than the last. So the expensive appends are spread further and further apart.
the appends the size the work
------------------ --------- ------------------
1 to 4 4 4 steps
5 to 8 8 8 steps, and a copy of 4
9 to 16 16 16 steps, and a copy of 8
the total for 16 16 28 steps, not 16 times 16
So the total work for n appends is about two n, which means that the average cost of one append is O of 1. That is what amortized means here. It is a guarantee about the whole sequence, not a hope about the average input.
The next question in this topic looks at the difference between this and the average case.