ArrayList is backed by a plain Object[]. A single add is O(1) when there's spare capacity — just write to the next slot and bump size. The subtlety is what happens when the backing array is full.
The resize
When size == capacity, add must grow: allocate a bigger array, copy every existing element over (O(n)), then append. Java's ArrayList grows by roughly 1.5× (newCap = old + (old >> 1)). That one resize is O(n) — so how is add "O(1)"?
Why it amortizes to O(1)
The key is that resizes are rare and the copy cost is shared across many cheap appends. Suppose we double on each resize (the cleanest version of the argument). Going from 0 to n elements, resizes happen at sizes 1, 2, 4, 8, … n. The total copy work is:
1 + 2 + 4 + 8 + ... + n = 2n - 1 = O(n)
That's O(n) total copying spread over n appends → O(1) amortized per append. The geometric growth is what makes the series converge to a constant multiple of n. If instead you grew by a fixed amount (say +10 each time), resizes would happen O(n) times and total copy work would be O(n²) — amortized O(n) per add. Geometric growth is the whole trick.
| Operation | Best | Average | Worst | Note |
|---|---|---|---|---|
| add (append) | O(1) | O(1) | O(n) | amortized O(1); worst case is the resize-and-copy |
| get / set | O(1) | O(1) | O(1) | direct index into backing array |
| add(i, x) / remove(i) | O(1) | O(n) | O(n) | shifts all elements after i |