A dynamic array sometimes has to copy all its elements, yet we say appending is O(1). Amortized analysis explains why both statements are true.
The expensive moment
When a dynamic array is full, it allocates a larger block and copies every element across. That single append costs O(n). If every append worked this way, building an array of n items would be O(n²).
Doubling spreads the cost
Suppose the capacity doubles each time it fills. Copies happen at sizes 1, 2, 4, 8, and so on. Over n appends, the total copying work is 1 + 2 + 4 + … which sums to less than 2*n*. Add the n ordinary writes and the total is under 3*n*. Divided across n operations, that is a constant amount per append: O(1) amortized.
Amortized is not average-case
Average-case analysis depends on a probability distribution over inputs. Amortized analysis makes a guarantee about the total cost of any sequence of operations, with no randomness involved. Individual operations may be expensive, but the total over the whole sequence is bounded.
The growth rule matters
Growth must be multiplicative. If the array grew by a fixed number of slots each time, the copies would add up to O(n²) overall, and appends would be O(n) amortized.
How to say it in an interview
Say that appending is amortized O(1) because occasional resizes are paid for by many cheap appends. If the interviewer asks about latency-sensitive systems, add that a single append can still take O(n), which matters when you need predictable worst-case response times.
Continue with the book
Explore the full treatment, worked examples, and exercises in Algorithmic Edge.
Adapted from Algorithmic Edge, published by Choral Software. Article text and original examples © 2026 Choral Software. All rights reserved.