Amortisation snapshot: list append

Intermediate Asymptotics & empirical timing

Created by Pavel · 29.04.2026 at 19:08 UTC

CPython list is a dynamic array: appending usually takes O(1) time, but occasionally triggers a resize that copies all elements to a larger buffer—an O(n) event. Amortised analysis spreads that rare cost across many cheap appends so the average cost per append is still O(1).

This matters when you build large lists incrementally (collecting batch IDs, logging events) versus preallocating when you know the final size ([None]*n or list comprehensions).

Amortised complexity is not the same as worst-case per operation: a single append can still be linear when resize fires.

List docs: [1].

Sources

[1]https://docs.python.org/3/tutorial/datastructures.html Return to text

University approvals: 0

Tasks

Question 1

The amortised time per list.append in CPython is typically:

Hint

Geometric resizing argument.

O(n)

O(1)

O(log n)

O(n²)

Question 2

A single list.append when the underlying buffer is full can take Θ(n) time because:

Hint

Resize copies elements to a larger table.

Python sorts the list on each append

The list may reallocate and copy all existing references to a new buffer

The GIL allocates n threads

Garbage collection always traverses the whole heap

Question 3

grow_append(n) builds [0, 1, ..., n-1] by starting from [] and appending in a loop (illustrate dynamic-array growth pattern).

Hint

Repeated append builds the list.

def grow_append(n: int):
    pass

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

1 test case will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Asymptotics & empirical timing
Difficulty: Intermediate
Completed: 0 users

Creator

Pavel