Amortized Analysis
Why ArrayList.add is O(1) 'on average' even though it sometimes copies everything: amortized cost and the doubling trick.
On this page
Here's a puzzle: adding to an ArrayList is documented as O(1), but sometimes adding one element
forces Java to copy the entire backing array, which is O(n). How can an operation that occasionally
does O(n) work be called O(1)? The answer is amortized analysis - and it's a favorite interview
follow-up.
Averaging cost over a sequence
Amortized analysis asks not "what's the worst case for one operation?" but "what's the average cost per operation over a long sequence?" Some operations are cheap and one is occasionally expensive; if the expensive ones are rare enough, the average stays low.
ArrayList.add is the classic example. Most adds just drop the element into the next free slot -
O(1). But when the backing array is full, Java allocates a bigger array (typically ~1.5×) and
copies everything over - O(n). The trick is in how it grows.
Why doubling makes it O(1) amortized
Suppose the array doubles when full. Starting from size 1 and adding n elements, the expensive
copy operations cost 1 + 2 + 4 + 8 + … + n - and that sum is about 2n, not n^2. Spread across
n adds, that's roughly 2 copies per add on average: a constant. So each add is O(1)
amortized, even though individual adds can spike to O(n).
// conceptually, what a growable array does on add:
if (size == capacity) {
capacity = capacity * 2; // rare: double the capacity
elements = Arrays.copyOf(elements, capacity); // O(n) copy, but only occasionally
}
elements[size++] = value; // usual case: O(1)The reason doubling works and, say, "grow by one each time" doesn't: if you grew by a fixed amount, you'd copy on almost every add, and the total becomes O(n^2). Geometric growth makes the expensive events exponentially rare, so their total cost stays linear.
Amortized ≠ average-case
They sound similar but differ. Average-case is about random inputs (e.g. hashing assuming a good distribution). Amortized is a guarantee over a sequence of operations with no randomness - the worst-case total for n operations, divided by n. Amortized O(1) means any n adds cost O(n) total, guaranteed.
You pay a small fixed fee most months, but every couple of years you buy a new phone - a big one-time cost. Nobody says your phone habit costs the price of a phone per month; you amortize that purchase across all the cheap months, and your true average monthly cost is small. A growable array does the same: the rare, expensive resize is spread across all the cheap adds, so the average per add is constant.
An interviewer says: "You claim ArrayList.add is O(1), but I can see it copies n elements when it resizes - that's O(n)." Explain, using the doubling strategy, why the amortized cost is still O(1), and what would break if the list grew by a fixed +1 slot instead of doubling.
Why is ArrayList.add O(1) amortized despite occasionally copying the whole array?
Key takeaways
- Amortized analysis measures the average cost per operation over a whole sequence, not the worst single operation.
- ArrayList.add is O(1) amortized: most adds are O(1), and rare O(n) resizes are spread thin.
- Doubling (geometric growth) makes resizes exponentially rare, so total copy cost over n adds is O(n).
- Growing by a fixed amount would resize almost every add, making the total O(n^2).
- Amortized (guarantee over a sequence) is different from average-case (expectation over random inputs).