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 is 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

It's amortized O(1), not O(1).

Let's say the list reserved size is 8 elements and it doubles in size when space runs out. You want to push 50 elements.

The first 8 elements push in O(1). The nineth triggers reallocation and 8 copies, followed by an O(1) push. The next 7 push in O(1). The seventeenth triggers reallocation and 16 copies, followed by an O(1) push. The next 15 push in O(1). The thirty-third triggers reallocation and 32 copies, followed by an O(1) push. The next 17 push in O(1).

So all of the pushes have O(1) complexity, we had 56 copies at O(1), and 3 reallocations at O(n), with n = 8, 16, and 32. Note that this is a geometric series and asymptotically equals O(n) with n = the final size of the list. That means the whole operation of pushing n objects onto the list is O(n). If we amortize that per element, it's O(n)/n = O(1).