Why appending to a list is amortized O(1)

Arrays, strings and hash maps Junior Python 3.13+ Reviewed By Best Latest Apps

Predict the output

A list doubles its capacity when full, starting at 1. How many element copies happen over 16 appends?

Python 3.13
cap, size, copies = 1, 0, 0
for _ in range(16):
    if size == cap:
        copies += size
        cap *= 2
    size += 1
print(copies)

Options

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

Show answer

Answer: A 15

Right: copies of 1, 2, 4 and 8 elements add up to 15, fewer than the 16 appends.

Total copying stays under one copy per append, which is the amortized O(1) bound in numbers.

Why not the others?
  • B 120. That is what copying on every append would cost.
  • C 16. The first append fits without a copy, and the last growth happened at size 8.

30-second answer

When a list runs out of room, it allocates a bigger block and copies everything, which is O(n). It grows by a fixed proportion, so copies get rarer as the list gets bigger, and the total copying for n appends is O(n). Spread over n appends, that is O(1) each on average: amortized O(1).

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

Explain why append is amortized O(1).

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

  • Occasional O(n) copy
  • Geometric growth
  • Total under 2n

Deep dive

With doubling, the copies for n appends add up to about 1 + 2 + 4 + ... + n, which is under 2n.

CPython grows lists by roughly an eighth plus a little, not by doubling; any growth by a constant factor gives the same amortized bound.

Amortized is not worst case: one unlucky append can still take O(n), which matters for latency-sensitive code.

Common mistakes

  • Calling append O(n) because of the occasional copy.
  • Thinking inserting at the front is cheap too: insert(0, x) shifts every element and is O(n).

Senior take & follow-ups

Say 'geometric growth' and 'amortized' together, and give the 2n bound. That is the whole argument.

Follow-up questions

Think of your answer first, then open the hint.

  1. How would you get O(1) at both ends?

    Show hint

    Use collections.deque, which supports appends and pops at both ends in O(1).

  2. What if you know the final size?

    Show hint

    Preallocate with [None] * n or build with a comprehension to skip regrowth.

Similar on iOS: Copy-on-write Swift arrays grow the same way but also copy on write when shared; Python lists are reference types and never copy on assignment.

What each operation costs: Arrays · Dynamic Arrays · Hash Table · Hash Functions

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.