Amortised cost: cheap on average, sometimes slow

Complexity analysis Mid-level Python 3.13+ Reviewed By Best Latest Apps

Predict the output

This tracks how many times a list's storage grows. What does it print?

Python 3.13
import sys
xs: list[int] = []
growths = 0
last = sys.getsizeof(xs)
for i in range(10_000):
    xs.append(i)
    size = sys.getsizeof(xs)
    if size != last:
        growths += 1
        last = size
print(growths < 100, len(xs))

Options

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A True 10000

Right: storage grows only a few dozen times for 10,000 appends.

Because each resize makes room for proportionally more items, the copying averages out to a constant per append.

Why not the others?
  • B False 10000. Growth is proportional, so resizes are rare.
  • C True 100. The list holds all 10,000 items.

30-second answer

Amortised cost averages over a sequence of operations in the worst case. A Python list grows its storage by a constant factor when full, so one append occasionally copies everything (O(n)), but those copies are rare enough that n appends cost O(n) in total: O(1) each, amortised. Average case is different: it averages over possible inputs, like hash lookups with random keys.

Practise saying it · 45 s. No recording, just a timer

Explain amortised O(1) append.

Say your answer out loud, then check which of these points you covered:

  • Occasional O(n) resize
  • Proportional growth
  • Total O(n) for n appends

Deep dive

The doubling (or ×1.125-ish in CPython) growth is what makes the total linear; growing by a fixed amount would make it quadratic.

Amortised bounds hold for every sequence; average-case bounds can fail on bad inputs.

Real-time systems may care about the rare O(n) step even when the amortised cost is fine.

Common mistakes

  • Calling list append 'O(n)' because resizing exists.
  • Calling hash map lookups 'amortised O(1)'; they are average-case O(1), and resizing makes inserts amortised.

Senior take & follow-ups

Separate amortised from average-case in one sentence; interviewers notice the difference.

Follow-up questions

Think of your answer first, then open the hint.

  1. How does a deque avoid big copies?

    Show hint

    CPython's deque is a linked list of fixed-size blocks, so it never copies the whole thing.

  2. Which other structures are amortised?

    Show hint

    Union-find with compression, splay trees, and the monotonic stack pattern.

What each operation costs: Bubble Sort · Merge Sort · Binary Search

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.