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: some implementations also shrink the internal array when many elements are removed, so a list that was once huge does not hold on to the memory forever. Others never shrink on their own and leave that to an explicit call.

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.

Is this true in every language? The principle is, the numbers are not. Every mainstream growable array works this way: Java ArrayList, C# List<T>, C++ std::vector, Python list, Rust Vec, Go slices with append. What differs is the growth factor and the shrinking policy:

Any constant factor above 1 keeps add amortised $O(1)$; a smaller factor wastes less memory but copies more often. Plain fixed arrays (int[] in Java, C arrays) do not grow at all, and a linked list never copies but pays for it elsewhere.

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.