dynamic-array table doubling

A plain array has a fixed size, but you often want a list that grows on demand — push items one at a time without knowing the final count. A dynamic array (the engine behind a vector or an ArrayList or a Python list) does this by keeping a fixed-size block of memory and, when that block fills up, allocating a bigger block and copying everything over. Table doubling is the policy of making the new block twice as big each time it fills, and it is the textbook example where amortized analysis explains a surprising efficiency.

Here is the mechanism for n appends starting from capacity 1. Most appends just write into a free slot in O(1). But whenever the array is full, an append first allocates a new array of double the capacity and copies all current elements over — an O(current size) step. Resizes happen at sizes 1, 2, 4, 8, ..., up to n, so the copying work totals 1 + 2 + 4 + ... + n/2, which is less than n. The simple writes total n. So all n appends together cost under 2n, and the amortized cost per append is O(1) even though a single resizing append costs O(n). You can prove this three ways: aggregate (sum the geometric series above), accounting (charge 3 per append, banking 2 on each new element to prepay its eventual copy), or potential (Phi = 2*size - capacity).

Doubling is what makes dynamic arrays practical, and the factor 2 is not magic — any constant growth factor greater than 1 (1.5 is common) gives amortized O(1), because the resize costs still form a geometric series. The honest warnings: growing by a fixed ADDITIVE amount (say, +10 slots each time) destroys the bound and makes appends amortized O(n); doubling can waste up to half the allocated memory right after a resize; and a single append still costs O(n) in the worst case, so dynamic arrays are a poor fit when every individual operation must be fast, as in hard real-time systems.