Glossary: Data Structures and Algorithms

Amortized O(1)

Also written: amortized

A cost that is O(1) on average over many operations, even though an occasional one is slow. Python's list `append` is amortized O(1) because the rare move to a bigger block is spread over many appends.