Why is the time complexity of Python's list.append() method O(1)?

Question

As seen in the documentation for TimeComplexity, Python's list type is implemented using an array.

So if an array is being used and we do a few appends, eventually you will have to reallocate space and copy all the information to the new space. After all that, how can it be O(1) worst case?

Answer 1

If you look at the footnote in the document you linked, you can see that they include a caveat:

These operations rely on the "Amortized" part of "Amortized Worst Case". Individual actions may take surprisingly long, depending on the history of the container.

Using amortized analysis, even if we have to occasionally perform expensive operations, we can get a lower bound on the 'average' cost of operations when you consider them as a sequence, instead of individually.

So, any individual operation could be very expensive - O(n) or O(n^2) or something even bigger - but since we know these operations are rare, we guarantee that a sequence of O(n) operations can be done in O(n) time.