What is the complexity of inserting at the end of a list (Python list)? Why is it sometimes O(n)?

Inserting an element at the end of a Python list usually has an amortized complexity of O(1). This is because the list is implemented as a dynamic array, which allocates some extra space.

However, sometimes the operation takes O(n), when the current allocated buffer is full, and a new larger array needs to be allocated and all elements copied. This copying results in linear complexity at that moment.

Example:

lst = [1, 2, 3]
lst.append(4)  # Usually O(1)

But if the internal buffer is full, Python will allocate a new array, copy the old elements, and add the new one — which is O(n).