Why is the Time Complexity of Python’s list.append() Method O(1)?

Python lists are implemented as dynamic arrays. When you use the append() method, Python may sometimes resize the underlying array, but this resizing doesn’t happen every time.

Appending to a list is considered amortized O(1) time complexity. Here’s why:

When the array runs out of space, Python allocates a larger block of memory (usually more than double the current size) and copies all elements to the new space. This copy operation is costly, but it doesn’t happen with every append. Most of the time, appends go into already-allocated space.

While a single append may take O(n) during a resize, over many append operations, the average time per append remains constant.

my_list = []
for i in range(1000):
   my_list.append(i)

Even though a few of these operations may trigger a resize and copy, the majority complete in constant time, making the average time per operation O(1).

This technique is known as amortized analysis, and it’s a common strategy in dynamic array implementations across languages.

Also Read:

Python With Machine Learning