Amortised cost

Some operations are cheap most of the time and expensive once in a while. Amortised cost is their average cost over a long run of them. The classic case is adding to the end of a dynamic array, a list that grows as you add to it.

Most appends just write into one free slot. When the array is full, it makes a new one twice the size and copies everything across. Because the size doubles each time, all that copying over n appends adds up to less than 2n.

So each append is O(1) amortised, even though a single one can cost O(n). Learn this now. It is why list append, hash map insert and several later structures are called constant time.