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. 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.
A common example is the dynamic array. If we have already allocated memory for a new entry, adding it will be O(1)
. If we haven’t allocated it we will do so by allocating, say, twice the current amount. This particular insertion will not be O(1)
, but rather something else.
What is important is that the algorithm guarantees that after a sequence of operations the expensive operations will be amortised and thereby rendering the entire operation O(1)
.