An array-list wraps a plain array and resizes it automatically; an add into a free slot is $O(1)$, but an add into a full array first copies every element into a bigger one, which is $O(n)$.

* The fourth add fits; the fifth finds the array full and pays for copying all four first. *

A plain array has a fixed length that is decided when it is created. An array-list hides that limitation: it keeps an internal array that is usually a bit larger than needed, plus a counter of how many slots are actually used.

• Room left: add writes the element into the next free slot and bumps the counter. One write, independent of $n$ — $O(1)$.
• Array full: there is nowhere to write. The list allocates a new, larger array (typically double the size), copies all $n$ existing elements across, and only then writes the new one. The copy touches every element — $O(n)$.
• Shrinking: when many elements are removed, the array-list can also shrink its internal array again, so a list that was once huge does not hold on to the memory forever.

So the cost of a single add depends on when you call it, which is why the worst case of one operation and the typical cost differ so sharply.

Go deeper:

• Dynamic array — capacity vs. size, the growth factor, and the performance table against linked lists.
• java.util.ArrayList — the Java implementation; its class comment states the amortised constant-time add.

Doubling makes the expensive copies so rare that their total cost is proportional to the number of adds — on average each add costs $O(1)$ (amortised). Growing by a constant amount makes every few adds pay a full copy, giving $O(n^2)$ for $n$ adds.

* The spikes get taller but twice as far apart, so the average never climbs. *

Count the copying work for $n$ adds, starting from capacity 1.

Doubling. Copies happen when the array holds 1, 2, 4, 8, … elements. The total copied is

$$1 + 2 + 4 + \dots + \frac{n}{2} < n$$

so $n$ adds cost fewer than $n$ writes plus fewer than $n$ copies: $O(n)$ in total, $O(1)$ per add on average. Each expensive copy is "paid for" by the many cheap adds since the last one.

Growing by 1 (or by any constant $k$). Every add (or every $k$-th add) copies the whole array, so the copies cost $1 + 2 + 3 + \dots + n$ — Gauss's sum, $O(n^2)$ in total, $O(n)$ per add.

This averaging over a sequence of operations is called amortised analysis. It is not an average over random inputs: it is a guarantee that any sequence of $n$ adds costs $O(n)$, even though one individual add can cost $O(n)$.

Tip: that is why a runtime table may list addLast on an array-list as $O(n)$ (the worst single call) while the Java documentation promises "amortised constant time". Both are true; they answer different questions.

Go deeper:

• Amortized analysis — the aggregate, accounting and potential methods, with the dynamic array as the worked example.
• MIT 6.006 — Data Structures and Dynamic Arrays (Erik Demaine) — full lecture deriving the amortised $O(1)$ append.