Course contentsShow
← Java
Lesson 1016 of 2,87024. List ImplementationsFree lesson

Amortized Analysis: Why O(1) Despite Occasional O(n)

How the cost of resizes is spread across many adds, yielding constant amortized time.

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).