Arrays and Dynamic Arrays
Imagine building a text editor that must store keystrokes. Or a database index that must serve millions of lookups per second. Both need a structure that gives instant access to the k-th item. Both also need to grow as data arrives without predictable bounds. The plain array solves the first problem perfectly. It solves the second problem not at all — its size is frozen at creation. The dynamic array resolves this tension with a simple but subtle trick. Over-allocate, and when you run out of room, grow geometrically rather than by a fixed increment. This single design decision is one of the most consequential ideas in practical computer science. Specifically: grow by doubling (or by any constant factor) instead of by a constant amount. It underlies Python's `list`, Java's `ArrayList`, C++'s `std::vector`, Go's slices, and Rust's `Vec`. Get the growth factor right, and appending elements costs O(1) time on average. This holds even though occasional resizes cost O(n). Get it wrong (grow by a constant number of slots each time), and the same workload silently degrades. It becomes O(n) per append, turning a linear-time algorithm into a quadratic-time one. This is a bug class real systems have shipped and later had to fix. The big picture is this: arrays exploit the contiguous memory model. Here, consecutive logical indices map to consecutive physical addresses. This enables arithmetic address computation and O(1) random access. Dynamic arrays layer a resizing policy on top of this model. They trade a small amount of wasted space and occasional bulk copying. In return, they offer the illusion of unbounded, cheap growth. Understanding why the amortized cost stays constant matters greatly. This can be shown via a clean potential-function or aggregate argument. Doing so is what separates knowing the trick from understanding the guarantee. This article gives the precise mechanics of both structures. It covers how addresses are computed and how resizing works step by step. It includes a full complexity derivation with a rigorous amortized-analysis proof. It also offers a worked trace showing the doubling pattern in action. Finally, it covers classic pitfalls — linear growth, shrink-thrashing, iterator invalidation — that trip up even experienced engineers.
- A fixed-size array stores elements contiguously; index `i` is found by one arithmetic computation, giving O(1) random access.
- A dynamic array wraps a fixed-size backing array with a `size` (logical count) and `capacity` (allocated slots), reallocating when full.
- Growing capacity by a constant multiplicative factor (e.g., doubling) makes amortized append cost O(1); growing by a constant additive amount makes it Θ(n).
- The proof uses aggregate or potential-function amortized analysis: total cost of n appends is O(n), so average cost per append is O(1).
- Insertion/deletion in the middle costs O(n) due to shifting; only end operations are cheap.
- Dynamic arrays are the backbone of Stacks, Queues and Deques, are used to implement Binary Heaps, and their addressing scheme underlies Hash Tables and Direct Addressing.
Random access is O(1) because of address arithmetic on contiguous memory; amortized O(1) append is possible only because geometric (not additive) resizing makes the total cost of n operations linear in n.
The idea
An array is a data structure storing a sequence of elements at contiguous memory locations, indexed by consecutive integers starting at 0 (or 1, by convention). Because elements have a fixed, known size `s` bytes, and the array begins at a known base address `B`, the memory address of element `i` is computed directly: ``` address(i) = B + i s ``` This is a single multiplication and addition — genuinely O(1) time, independent of array size or of `i`. This is the defining advantage of arrays over pointer-linked structures: <strong>random access</strong> requires no traversal, only arithmetic. The cost is rigidity: the array's capacity is fixed at allocation time, since contiguity demands that the whole block be reserved in advance. A <strong>dynamic array</strong> (also called a growable array, resizable array, or — in many languages — simply "array" or "list") removes this rigidity by decoupling two quantities: the <strong>size</strong> (number of elements logically stored, sometimes called length) and the <strong>capacity</strong> (number of slots physically allocated in the backing array). The dynamic array is a thin wrapper: a pointer to a backing fixed-size array, plus `size` and `capacity` counters. Appending an element is O(1) when there is spare capacity — just write into the next free slot and increment `size`. The interesting case is what happens when `size` reaches `capacity`: the structure must <strong>reallocate</strong> — allocate a new, larger backing array, copy all existing elements over, free the old array, and only then write the new element. This copy step costs Θ(current size), so any single append can be expensive. The central design question, and the subject of the correctness argument below, is how much larger* the new array should be — and the answer (grow by a constant multiplicative factor) is what guarantees good performance averaged over a long sequence of appends, a guarantee formalized through amortized analysis.
How it works
Fixed-size array operations. Read and write at index `i` are both O(1): compute the address, dereference. Bounds checking (verifying `0 ≤ i < capacity`) is typically O(1) as well, just an added comparison.
Dynamic array operations. The structure maintains three fields: `data` (pointer to backing array), `size`, and `capacity`. The key operation is `push_back` (append), which triggers the growth policy on overflow. ``` structure DynamicArray: data: pointer to array of capacity slots size: integer // number of elements in use capacity: integer // number of allocated slots function GET(A, i): if i < 0 or i >= A.size: error "index out of bounds" return A.data[i] // O(1): address = base + i elemSize function SET(A, i, value): if i < 0 or i >= A.size: error "index out of bounds" A.data[i] = value // O(1) function PUSH_BACK(A, value): if A.size == A.capacity: RESIZE(A, max(1, 2 A.capacity)) // growth factor = 2 A.data[A.size] = value A.size = A.size + 1 // O(1) amortized, O(n) worst case function RESIZE(A, newCapacity): newData = allocate array of newCapacity slots for i = 0 to A.size - 1: newData[i] = A.data[i] // Θ(size) copy free(A.data) A.data = newData A.capacity = newCapacity function POP_BACK(A): if A.size == 0: error "empty" A.size = A.size - 1 // optional: shrink if A.size <= A.capacity / 4, halve capacity return A.data[A.size] function INSERT_AT(A, i, value): if i < 0 or i > A.size: error "index out of bounds" if A.size == A.capacity: RESIZE(A, max(1, 2 A.capacity)) for j = A.size downto i + 1: A.data[j] = A.data[j - 1] // shift right, Θ(size - i) A.data[i] = value A.size = A.size + 1 function DELETE_AT(A, i): if i < 0 or i >= A.size: error "index out of bounds" for j = i to A.size - 2: A.data[j] = A.data[j + 1] // shift left, Θ(size - i) A.size = A.size - 1 ``` Three details matter for correctness. First, `RESIZE` always copies existing elements <strong>before</strong> freeing the old array — losing this ordering corrupts data. Second, the growth factor must be a constant greater than 1 (2 is common; some implementations use 1.5 to reduce peak memory waste); an additive* policy (`capacity += 1` or `capacity += k` for fixed `k`) breaks the amortized guarantee, as proven below. Third, an optional shrink policy (halve capacity when size drops to a quarter of capacity, not a half) avoids thrashing — repeatedly resizing on alternating push/pop right at a boundary.
Complexity & correctness
Fixed array. `GET`/`SET` are O(1) worst case: one address computation, one memory access — no dependence on `n`. Space is Θ(n) for `n` elements, with zero overhead beyond the elements themselves.
Dynamic array — amortized append. `PUSH_BACK` is O(1) in the common case (spare capacity exists) and Θ(n) in the resize case (must copy all `n` current elements). The claim is that despite these occasional expensive operations, any sequence of n `push_back` calls starting from an empty array costs O(n) total time, i.e., O(1) amortized per call. Aggregate-method proof. Suppose capacity doubles (1, 2, 4, 8, …, 2^k) and resizes happen exactly when size reaches the current capacity. Starting from capacity 1, after `n` pushes the resizes occur at sizes 1, 2, 4, 8, …, up to the largest power of 2 less than `n`. The total work done by resize-copies is: ``` 1 + 2 + 4 + 8 + ... + 2^(k-1) where 2^k is the first capacity ≥ n ``` This is a geometric series summing to `2^k - 1 < 2n - 1 < 2n`. Adding the `n` O(1) writes for the pushes themselves, total work is bounded by: ``` n + 2n = 3n = O(n) ``` Dividing by `n` operations gives O(1) amortized cost per push. The geometric structure is essential: each resize is twice as expensive as the last, but resizes are also twice as rare, so the doubling of cost is exactly cancelled by the halving of frequency — the series converges (geometric decay) rather than growing (as an arithmetic series would). Why additive growth fails. If instead capacity grows by a fixed constant `c` each time (`capacity += c`), resizes happen after every `c` pushes, and the `k`-th resize copies roughly `kc` elements. Over `n` pushes there are `n/c` resizes, and total copying work is: ``` c + 2c + 3c + ... + (n/c)·c = c · (1 + 2 + ... + n/c) = Θ(n²/c) ``` For fixed `c` this is Θ(n²) total, i.e., Θ(n) amortized per push — no better than never batching at all. This is the historical bug: early or naive implementations that grow "by 10" or "by 1 slot" quietly turn a linear workload quadratic. Potential-function proof (equivalent, more general). Define a potential function: ``` Φ(A) = 2 · A.size − A.capacity ``` Φ is 0 right after a resize (when `size = capacity/2`, immediately after doubling — check the invariant `capacity ≥ size ≥ capacity/2` holds after every resize) and grows as `size` approaches `capacity`, reaching `Φ = capacity` exactly when full. Define amortized cost = actual cost + ΔΦ.
- Non-resizing push: actual cost = 1 (the write). `size` increases by 1, so ΔΦ = 2. Amortized cost = 1 + 2 = 3 = O(1).
- Resizing push: actual cost = `size + 1` (copy all `size` old elements, plus the new write). Capacity doubles from `size` to `2·size`, and `size` becomes `size+1`. Before: Φ = `2·size − size = size`. After: Φ = `2(size+1) − 2·size = 2`. So ΔΦ = `2 − size`. Amortized cost = `(size + 1) + (2 − size) = 3 = O(1)`.
Both cases give amortized cost O(1), and since Φ ≥ 0 always and Φ starts at 0, the sum of amortized costs upper-bounds the sum of actual costs — proving the total actual cost of `n` pushes is O(n). This potential-function argument generalizes cleanly to any growth factor `α > 1` (not just 2), giving amortized cost `O(α/(α−1))`, which is O(1) for any fixed `α > 1` but blows up as `α → 1⁺` — matching the intuition that a growth factor too close to 1 approaches additive growth.
Other operations. `GET`/`SET` remain O(1) (unaffected by the wrapper). `INSERT_AT`/`DELETE_AT` at arbitrary index `i` cost Θ(n − i) for the shift, so Θ(n) worst case (inserting/deleting near the front) — dynamic arrays are efficient only at the end. `POP_BACK` is O(1) (with optional amortized O(1) shrinking, using the mirrored argument: shrink by half when size falls to a quarter of capacity, not a half, to avoid oscillation between grow and shrink on alternating push/pop at a threshold).
Space. A dynamic array uses Θ(n) space for `n` elements, with a worst-case overhead factor of up to 2× (capacity can be up to roughly double the size right before a resize) — a small, bounded price for O(1) amortized growth.
Worked example
Trace `PUSH_BACK` calls A, B, C, D, E, F, G onto an initially empty dynamic array with capacity-doubling starting from capacity 1.
| Call | size before → after | capacity before → after | Action | Cost |
|---|---|---|---|---|
| push A | 0 → 1 | 0 → 1 | size==cap(0), resize to 1, write A | resize copies 0, write 1 → cost 1 |
| push B | 1 → 2 | 1 → 2 | size==cap(1), resize to 2 (copy A), write B | copy 1 + write 1 → cost 2 |
| push C | 2 → 3 | 2 → 4 | size==cap(2), resize to 4 (copy A,B), write C | copy 2 + write 1 → cost 3 |
| push D | 3 → 4 | 4 → 4 | spare slot, write D | cost 1 |
| push E | 4 → 5 | 4 → 8 | size==cap(4), resize to 8 (copy A,B,C,D), write E | copy 4 + write 1 → cost 5 |
| push F | 5 → 6 | 8 → 8 | spare slot, write F | cost 1 |
| push G | 6 → 7 | 8 → 8 | spare slot, write G | cost 1 |
Total actual cost over 7 pushes: `1+2+3+1+5+1+1 = 14`. Compare to `3n = 21` — well within the O(n) bound proven above; average cost per push is `14/7 = 2`, consistent with O(1) amortized (note the bound `3n` is an upper bound, not tight, which is expected of aggregate-analysis bounds). Notice the pattern: expensive resizes (cost 1, 2, 4, i.e., copies of size 0,1,2,4) occur at pushes 1, 2, 3, 5 — precisely when `size` was a power of two before the push — and get exponentially rarer as capacity grows, which is exactly the mechanism the geometric-series proof formalizes. Now contrast with additive growth by `c = 1` (capacity always exactly `size` before, `size+1` after — the worst case, equivalent to "grow by one slot each time"): every single push resizes, copying all existing elements.
| Call | copy cost | write cost | total |
|---|---|---|---|
| push A | 0 | 1 | 1 |
| push B | 1 | 1 | 2 |
| push C | 2 | 1 | 3 |
| push D | 3 | 1 | 4 |
| push E | 4 | 1 | 5 |
| push F | 5 | 1 | 6 |
| push G | 6 | 1 | 7 |
Total: `1+2+3+4+5+6+7 = 28` for the same 7 pushes — already double the doubling policy's cost, and the gap widens quadratically as `n` grows (`Θ(n²)` versus `Θ(n)`), confirming the earlier derivation.
Common pitfalls & traps
| Pitfall | Why it happens | Fix |
|---|---|---|
| Additive growth (`capacity += k` for fixed `k`) | Seems "safer" / less wasteful per resize | Use a multiplicative factor > 1 (e.g., 1.5–2×) to guarantee O(1) amortized append |
| Shrink-thrash (halve capacity exactly when `size == capacity/2`) | Alternating push/pop at that boundary triggers resize on every call | Only shrink when `size ≤ capacity/4`, restoring to `capacity/2` |
| Off-by-one on capacity check | Checking `size < capacity` after incrementing, or resizing one push too late/early | Check `size == capacity` before writing, not after |
| Assuming O(1) worst-case append | Confusing amortized with worst-case; a single push can still cost Θ(n) | State guarantees precisely: O(1) amortized, O(n) worst case per call |
| Iterator/pointer invalidation after resize | `RESIZE` frees the old backing array and allocates a new one at a different address | Never retain raw pointers/references into a dynamic array across a push; re-fetch after mutation |
| Inserting/deleting at the front assumed cheap | Confusing dynamic array with a linked list | Use `push_back`/`pop_back` for O(1) ops; use a different structure (e.g. deque) if front operations dominate |
Pioneers & history
The array is older than modern computer science itself — it is essentially the mathematical notion of an indexed sequence, realized physically once machines had addressable memory. Its computational significance crystallized with the von Neumann architecture, in which a single addressable memory stores both instructions and data, making address arithmetic (and hence O(1) indexed access) a hardware-level primitive rather than an abstraction. The dynamic array's amortized-growth idea matured later, as a rigorous byproduct of the development of amortized analysis in the 1980s, which gave engineers a formal language ("aggregate method," "potential method," "accounting method") to justify what practitioners had already discovered empirically: doubling works, and additive growth doesn't.
Origins · 1 minJohn von Neumann and how this was discovered
Where this matters
Every general-purpose language ships a dynamic array as its default list type: Python's `list`, Java's `ArrayList`, C++'s `std::vector`, JavaScript's `Array`, Go's `slice`, Rust's `Vec`. Database engines use contiguous arrays for column-store buffers and for the leaf-level of some index structures, exploiting cache-friendly sequential access. Compilers and interpreters use dynamic arrays for operand stacks and symbol tables. Game engines and numerical libraries (e.g., NumPy) rely on the fixed-array addressing model for tight, vectorizable inner loops. The dynamic array is also the natural implementation substrate for the array-backed variants of Stacks, Queues and Deques (push/pop at one or both ends in O(1) amortized time), for Binary Heaps (a complete binary tree stored implicitly in an array, with parent/child indices computed arithmetically), and its address-arithmetic idea reappears directly in Hash Tables and Direct Addressing, where a hash function maps keys to array indices to retain O(1) expected access without requiring the keys themselves to be small integers.
Ask the tutor: How would the amortized-cost proof change if the array grew by a factor of 1.5 instead of 2?
Is array access really O(1), even for huge arrays?
Yes, in the standard random-access memory (RAM) model used in algorithm analysis. Computing `base + i elementSize` takes a constant number of arithmetic operations regardless of array length or index value, and dereferencing a memory address is treated as a constant-time hardware operation. In practice, very large arrays can suffer cache misses or virtual-memory page faults that make some accesses physically slower than others, but this is a constant-factor, hardware-level effect outside the RAM model's abstraction — the asymptotic* complexity remains O(1).
What exactly does "amortized O(1)" mean, and how is it different from "average case O(1)"?
Amortized complexity is a worst-case guarantee over a sequence of operations, not a probabilistic statement about inputs. "Amortized O(1) append" means: for any sequence of n appends (no assumption about input distribution), total cost is O(n), so the average cost per operation in that sequence is O(1). "Average-case" complexity, by contrast, usually assumes some probability distribution over inputs (e.g., random permutations) and bounds the expected cost. Amortized bounds hold deterministically for every sequence; they say nothing about any single operation's cost, which can spike to Θ(n).
Why not just allocate a huge array upfront to avoid resizing entirely?
You could, if you knew the maximum size in advance, but that defeats the purpose of a dynamic array and wastes memory when the real size is much smaller — potentially by orders of magnitude. Dynamic arrays let capacity track actual usage within a constant factor (never more than 2× waste with a doubling policy, and less with shrinking), while still guaranteeing O(1) amortized growth without any upfront knowledge of the final size. The tradeoff is bounded, predictable memory overhead versus unbounded flexibility.
Does inserting or deleting at an arbitrary index ever run in less than O(n) time?
Not with a plain array-backed structure: inserting or deleting at index `i` requires shifting all elements after `i` by one slot to preserve contiguity, costing Θ(n − i) in the worst case (Θ(n) for insertion/deletion near the front). Only operations at the very end (`push_back`/`pop_back`) avoid this shift. Structures like linked lists trade away O(1) random access to get O(1) insert/delete given a pointer to the location, while balanced trees or skip lists offer O(log n) for both — dynamic arrays are optimal specifically for indexed access and end-append, not general insertion.
What growth factor do real languages actually use, and does it matter?
Common choices are 2 (C++ `std::vector` in several implementations, Java's `ArrayList` historically used 1.5), and other implementations use factors between 1.25 and 2. Any constant factor α > 1 gives O(1) amortized append; smaller factors (closer to 1) waste less peak memory but resize more often, while larger factors waste more memory but resize less often. A factor of exactly 2 has a subtle downside: the sum of all previously freed backing arrays can never be reused to satisfy the next allocation (each new array is strictly larger than the sum of all previous ones), which is why some allocators prefer growth factors below the golden ratio (~1.618).
How does an array relate to structures like stacks, heaps, and hash tables?
An array is the physical substrate; many abstract structures are just an array plus a disciplined access pattern. A stack restricts access to one end of a dynamic array (push/pop at the back), giving O(1) amortized operations for free — see Stacks, Queues and Deques. A binary heap stores a complete binary tree implicitly in a plain array, using index arithmetic (`2i+1`, `2i+2`, `(i-1)/2`) instead of pointers — see Binary Heaps. A hash table uses a fixed-size array as its backing store and a hash function to compute an index from an arbitrary key, directly reusing the O(1) addressing guarantee — see Hash Tables and Direct Addressing. In each case, the array's contiguous-memory addressing is the performance foundation.
Can dynamic array resizing ever be avoided entirely, for truly O(1) worst-case append?
Yes, with more sophisticated designs. One technique incrementally copies a few old elements into the new array on every push leading up to a resize, spreading the copying cost evenly so that no single push is ever slower than O(1) — this converts amortized O(1) into worst-case O(1) at the cost of extra bookkeeping and temporarily holding two backing arrays simultaneously. Another approach uses a structure of geometrically-sized blocks (e.g., a "growable array of arrays") to avoid ever copying old data at all. These techniques are used in latency-sensitive real-time systems where an occasional Θ(n) spike, even if rare on average, is unacceptable.