List append() complexity

Question

Accepted Answer

Python lists over-allocate storage, so most appends just write to an already-reserved slot in O(1). Occasionally the buffer fills and Python copies the list to a larger allocation - that copy is O(n), but it happens so rarely that the cost spreads out to O(1) per append on average. The key word is "amortized" - the worst case exists, but it is not representative of typical behavior.