Analyze the memory growth algorithm of Python lists. Why is `append()` considered an amortized $O(1)$ operation despite occasionally triggering a full memory reallocation?
Python interview question for Advanced practice.
Answer
Python lists are implemented as dynamic arrays (contiguous blocks of pointers). When you create a list, Python allocates a specific amount of memory capacity. The Algorithm: When you append() an item and the list is full, Python does not allocate just one more slot. Instead, it allocates a significantly larger block (over-allocation), copies the existing items to the new block, and frees the old one. The growth factor is roughly 1.125x (specifically newallocated = newsize + (newsize 3) + 6). Amortized Complexity: Although the resize operation is expensive ($O(n)$), it happens rarely. For $N$ appends, you only resize $\log N$ times. If you average the cost of the few expensive resizes over the many cheap insertions, the cost per append() approaches constant time $O(1)$. This is crucial for performance; without it, building a list would be $O(n^2)$.
Explanation
CPython uses a growth pattern of approximately 1.125x (plus constant) to prevent frequent reallocations.