SESKStuff Everyone Should Know
SESK: Stuff Everyone Should Know · sesk.info/tech-dynamic-array-amortized

Appending to a dynamic array sometimes copies everything, yet it is still called O(1). Why?

It is O(1) amortized: the rare big copies average out over many cheap appends.

Start playing free

  1. The cost is O(1) averaged over many appends ✔
  2. Copying memory takes no time
  3. The array never actually grows

Why: When a dynamic array fills up, it moves to a much bigger block, often double the size. Those expensive copies happen so rarely that, spread across all the appends, each one costs a constant amount.

Huh, didn't know that: Python list append and pop from the end are amortized O(1), which is why building a list with append is fast.

The dad joke
My dynamic array said it would only grow once in a while. Then it doubled down.
Like this card?
Play the game

References

Answer: The cost is O(1) averaged over many appends. When a dynamic array fills up, it moves to a much bigger block, often double the size. Those expensive copies happen so rarely that, spread across all the appends, each one costs a constant amount.

  1. MIT 6.006 Introduction to Algorithms, Lecture 2: Data Structures ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/mit6_006s20_lec2
    Inserting into a dynamic array takes Θ(1) amortized time
    Checked 2026-10-10.

Think this answer is wrong? Tap "Challenge this answer" on the card in the game and tell us why.

Test yourself in the game

Tech & GadgetsWhy is inserting at the front of a Python list slow when appending at the end is fast?Tech & GadgetsHow fast is binary search on a sorted array of n items, in Big O terms?Tech & GadgetsIn Big O notation, what do you ignore when describing an algorithm's running time?

That's stuff everyone should know.