Amortized Analysis: Why O(1) Despite Occasional O(n)
What You'll Learn
You'll discover why ArrayList.add() is considered O(1) constant time even though it sometimes triggers an O(n) resize operation.
The Seeming Contradiction
You've learned that most add() calls just place an element at the end of the array—a fast O(1) operation. But occasionally, when capacity is exhausted, the ArrayList must allocate a new array and copy all existing elements using System.arraycopy(), which is O(n). So how can we claim add() is O(1)?
Spreading the Cost
Amortized analysis averages the cost of operations over a sequence, rather than focusing on the worst single case.
The Math Behind It
When ArrayList grows by 1.5× (the growth strategy you learned), each resize copies n elements but creates room for approximately 0.5n new additions before the next resize.
- One resize costs n operations
- But that cost is "paid for" by 0.5n cheap O(1) adds that follow
- Average cost per add: n / (0.5n) = 2 operations
- Constant! O(1) amortized time
Analogy: The Coffee Shop Punch Card
Imagine buying 9 coffees quickly at $3 each, then on the 10th purchase you must wait 10 minutes for a free reward coffee. Over those 10 visits, you averaged just 1 extra minute per visit—not 10 minutes each time. The occasional expensive operation is "smoothed out" across many cheap ones.
Why This Matters
Amortized O(1) means that even though individual add() calls can be slow, the total time for adding n elements remains O(n), not O(n²). ArrayList remains efficient for repeated additions.
Key Takeaway: Amortized analysis spreads the cost of occasional expensive resizes across many cheap adds, making ArrayList's add() operation O(1) on average, even though individual calls can be O(n).