Most appends write into free capacity in O(1). Occasionally the array resizes and copies O(n) elements; spread over many appends, the average cost per append stays O(1) (amortized).
let capacity = 4;
let size = 0;
function append(x: number) {
if (size === capacity) {
capacity *= 2; // resize + copy O(n)
}
size++;
}A dynamic array keeps a backing array with some extra capacity. Most appends just write into the next free slot (O(1)). When the array is full, it allocates a larger array (often 2x), and copies existing elements (O(n)).
Why amortized O(1)? Because resizing is rare. With doubling growth, the total amount of copying across N appends is O(N): each element gets moved a small number of times, so the average cost per append stays constant.
If capacity doubles, resizes happen at sizes 1, 2, 4, 8, 16... Total copied elements up to N is roughly 1 + 2 + 4 + ... + N = O(N).
let cap = 4
let size = 0
function append() {
if (size === cap) {
cap *= 2 // allocate + copy size elements (O(size))
}
size += 1 // write into free slot (O(1))
}