Static vs Dynamic Arrays

The Fundamental Question

Every programmer has typed something like arr.append(x) or arr.push(x) tens of thousands of times. It feels free. The list just gets longer, no questions asked. But arrays in physical memory are contiguous: a single block of bytes laid out one after another. There's no “just put it after the last element” — the slot after the last element belongs to some other variable, struct, or piece of code. So how does append work?

The answer is one of the most beautiful trade-offs in computer science: there are two fundamentally different kinds of array, and dynamic arrays are built on top of static ones. Understanding which is which — and the cost of converting between them — is the difference between code that scales and code that mysteriously stalls in production.

Why this matters: “Append is O(1)” is a half-truth. A single append can be O(n). What's actually true is the amortized cost is O(1) — and the amortized analysis itself is one of the most elegant arguments in algorithms.

Static Arrays: Fixed and Predictable

A static array has a size fixed at the moment of allocation. You ask the runtime for $N$ contiguous slots, you get them, and that's it forever. If you want a 101st element, tough — the slot after the 100th already belongs to someone else.

Notice how strict the typing is in C++, Rust, and Go: the size is part of the type. [100]int and [200]int are different types. This is intentional — it lets the compiler know the exact stack frame layout and emit instruction-level optimal code with zero allocation overhead.

The address formula

For an array $A$ with base address $B$ and element size $s$ bytes, accessing $A[i]$ takes one arithmetic step:

$\text{address}(A[i]) = B + i \cdot s$

That's why static-array indexing is $O(1)$: one multiply (often a shift, since $s$ is a power of two), one add, one memory load. The CPU does this in a single cycle.

Dynamic Arrays: Capacity vs Size

A dynamic array (also called a growable array, vector, or list) hides a static array under the hood and adds bookkeeping to make it grow. The key insight is that there are now two sizes:

1. Logical size $n$ — the number of elements the user actually stored.
2. Capacity $c$ — the number of slots actually allocated. Always $c \ge n$.

Slots between $n$ and $c$ are real memory but are logically empty — they hold uninitialized garbage from the user's perspective. len(arr) returns $n$, never $c$.

Append works in two cases:

• Cheap path ($n < c$): write the new value at slot $n$, then $n \leftarrow n + 1$. One store. $O(1)$.
• Expensive path ($n = c$): allocate a larger backing array of size $c'$, copy all $n$ existing elements, free the old buffer, then take the cheap path. $O(n)$.

The Growth Strategy: Why Doubling?

When the buffer is full, how much should we grow it by? This single decision separates $O(n)$ from $O(n^2)$ over a sequence of appends. There are three serious options.

Option A: Add a constant (e.g., +10 every time)

Every $10$ appends triggers a resize that copies $10, 20, 30, \ldots$ elements. After $n$ appends, the total copy cost is:

$10 + 20 + 30 + \cdots + n \;=\; \sum_{k=1}^{n/10} 10k \;=\; \frac{n(n+10)}{20} \;\in\; \Theta(n^2)$

That makes append $\Theta(n)$ amortized — disaster. Never grow by an additive constant.

Option B: Multiply by a constant (e.g., ×2 every time)

Resizes happen at sizes $1, 2, 4, 8, 16, \ldots, 2^k \le n$. The total copy cost is a geometric series:

$1 + 2 + 4 + \cdots + 2^k \;=\; 2^{k+1} - 1 \;<\; 2n \;\in\; O(n)$

So $n$ appends total $O(n)$ work, which means amortized $O(1)$ per append. This is the magic.

Option C: Multiply by 1.5

Same asymptotic story as ×2 (still $O(n)$ total), but with a twist that matters in practice. With factor 2, the new buffer is always strictly larger than the sum of all previously freed buffers — so the allocator can never reuse old slots. With factor $\phi \approx 1.618$ or smaller, recently-freed memory is large enough to satisfy the next allocation, reducing fragmentation.

Amortized Analysis: The Real Cost of Append

Let's prove the $O(1)$ claim directly using the aggregate method. Suppose we start with an empty dynamic array (capacity 1) and perform $n$ appends with doubling.

A resize is triggered exactly when $n$ reaches a power of two: at appends number $1, 2, 4, 8, \ldots, 2^{\lfloor \log_2 n \rfloor}$. The resize at size $2^k$ copies $2^k$ elements.

Total cost $T(n)$ = (n cheap writes) + (sum of all copy costs):

$T(n) \;=\; n + \sum_{k=0}^{\lfloor \log_2 n \rfloor} 2^k \;\le\; n + 2n \;=\; 3n$

So the amortized cost per append is $T(n)/n \le 3 = O(1)$. Three writes per append, no matter how large $n$ grows.

Interactive: Dynamic Array Builder

Click append repeatedly and watch the buffer fill. When it's full, the next append triggers a resize: the strip widens, every existing element is copied (the cost spike), and amber-tinted free slots appear at the right. Toggle the growth factor between 1.5× and 2× to see how often each strategy resizes.

Two things to notice as you click:

• The amortized cost per op stays close to a small constant (around 2–3) regardless of how many appends you do. That's the geometric series at work.
• With factor 1.5×, resizes happen more often (about every 1.5x in size) but each one copies fewer elements. Total work is the same up to constants. The visible difference is how much “slack” (amber free space) you carry: factor 2 has up to 50% slack just after a resize; factor 1.5 has up to 33%.

Operation Costs Side by Side

Here is the table you should commit to memory. Worst-case is the cost of a single operation in the unluckiest case; amortized is the long-run average over a sequence.

Three rows deserve a comment.

Why is prepend O(n)?

To insert at index 0, every existing element must shift one slot to the right to make room. That's $n$ moves regardless of capacity. No clever growth strategy fixes this. If you need fast prepend, use a deque (double-ended queue, Chapter 7) or a circular buffer.

Why is insert at index k actually O(n - k)?

Inserting at index $k$ shifts the suffix from $k$ to $n-1$ rightward — that's $n - k$ moves. Inserting near the end is cheap; near the front is expensive. Same logic for delete.

Why is access still O(1) on a dynamic array?

Because the backing storage is still a contiguous static array. $A[i]$ is one pointer dereference to the buffer, plus $B + i \cdot s$. The dynamic-vs-static distinction only matters at the moment of growth.

Implementation: A Dynamic Array From Scratch (Python)

Python's list is already a dynamic array, so to see the machinery we have to build one against raw memory. We'll use ctypes to allocate a fixed-capacity backing buffer.

If _n = 3 and _capacity = 8, asking for index 5 must raise IndexError.

_n=4, _capacity=4 triggers _resize(8). _n=2, _capacity=4 takes the cheap path.

If _capacity = 4, this calls _resize(8).

_resize(8) when _capacity=4: allocate B of length 8.

1import ctypes
2
3
4class DynamicArray:
5    def __init__(self):
6        self._n = 0
7        self._capacity = 1
8        self._A = self._make_array(self._capacity)
9
10    def __len__(self):
11        return self._n
12
13    def __getitem__(self, k):
14        if not 0 <= k < self._n:
15            raise IndexError("index out of range")
16        return self._A[k]
17
18    def append(self, obj):
19        if self._n == self._capacity:
20            self._resize(2 * self._capacity)
21        self._A[self._n] = obj
22        self._n += 1
23
24    def _resize(self, new_cap):
25        B = self._make_array(new_cap)
26        for k in range(self._n):
27            B[k] = self._A[k]
28        self._A = B
29        self._capacity = new_cap
30
31    def _make_array(self, c):
32        return (c * ctypes.py_object)()

Trace what happens with four appends starting from empty:

Total cost: 1 + (1 copy + 1 write) + (2 copies + 1 write) + 1 = $6$ writes for $4$ appends. Amortized 1.5 — well under our 3n upper bound.

Implementation: The Same Idea in C++

In C++ we have to manage memory by hand with new[] and delete[] — exactly the work that std::vector hides. (A production version would use std::allocator, placement new, move semantics, exception safety, and an iterator interface; we're showing the bones.)

size_=4, cap_=4 → resize(8) first.

1#include <cstddef>
2
3template <typename T>
4class Vector {
5private:
6    T* data_;
7    std::size_t size_;
8    std::size_t cap_;
9
10public:
11    Vector() : size_(0), cap_(1) {
12        data_ = new T[1];
13    }
14
15    ~Vector() {
16        delete[] data_;
17    }
18
19    std::size_t size() const { return size_; }
20
21    T& operator[](std::size_t i) {
22        return data_[i];
23    }
24
25    void push_back(const T& value) {
26        if (size_ == cap_) {
27            resize(2 * cap_);
28        }
29        data_[size_++] = value;
30    }
31
32private:
33    void resize(std::size_t new_cap) {
34        T* new_data = new T[new_cap];
35        for (std::size_t i = 0; i < size_; ++i) {
36            new_data[i] = data_[i];
37        }
38        delete[] data_;
39        data_ = new_data;
40        cap_ = new_cap;
41    }
42};

Real-World Implementations

Every serious language ships a dynamic array as its default sequence type. Each one tunes growth differently for its target use case.

Beyond “just a list”: the dynamic-array pattern in disguise

• Hash table internals — when load factor exceeds a threshold (typically 0.75), the bucket array is reallocated and every entry is rehashed into the larger array. Same allocate-copy-free pattern.
• String builders — Java's StringBuilder, Python's io.StringIO, and Rust's String are all dynamic arrays of bytes/chars under the hood. That's why repeatedly concatenating with += in a loop can be O(n²) in some languages but O(n) when using a builder.
• Database write-ahead-log buffers — bounded dynamic arrays. They grow up to a hard cap, then flush to disk and reset rather than grow further, giving worst-case bounds on memory.
• GPU memory pools and game-engine object pools — pre-allocated static arrays acting as a free list. Game engines pay the static-array cost up front to avoid GC pauses during a frame.
• Image and video buffers — almost always static. A 4K frame is a 3840×2160×4 byte chunk, allocated once at startup and reused every frame.

When NOT to Use Dynamic Arrays

Dynamic arrays are an excellent default, but they have failure modes. Reach for something else when:

Pitfalls and Gotchas

1. Iterator and pointer invalidation

In C++, holding a pointer or iterator into a std::vector across a push_back is undefined behavior — the resize may have moved the entire buffer to a different address. The same trap exists in Rust (the borrow checker prevents it at compile time) and in Go slices (an append may or may not return a slice pointing to the original backing array).

1std::vector<int> v = {1, 2, 3};
2int* p = &v[0];      // points into v's buffer
3v.push_back(4);      // may reallocate — p is now dangling
4*p = 99;             // undefined behavior!

2. Memory holes after pop

Most implementations don't shrink on pop. After pushing 1 million elements then popping all of them, capacity is still ~1 million. To release memory you have to call shrink_to_fit() (C++), construct a new list (Python), or assign a freshly-sized slice (Go).

3. Off-by-one in capacity vs size

Beginners writing their own dynamic array often get the resize trigger wrong. The condition is $n = c$, not $n > c$ or $n \ge c - 1$. Resize before writing the new element, not after.

4. Assuming append is “always fast”

It's amortized fast, not worst-case fast. If you're writing a 60-fps game loop and a single resize copies 100 MB, you'll drop a frame. Profile, and pre-reserve.

5. Confusing dynamic arrays with linked lists

A “list” in Python, JavaScript, Java, or Ruby is a dynamic array, not a linked list. The name is a historical accident inherited from LISP. If you want O(1) middle insertion, you need a different data structure entirely (Chapter 6).

Summary

The two big ideas to take away:

1. Capacity is not size. A dynamic array carries hidden slack so that most appends can skip allocation. The $(n, c)$ pair is the entire trick.
2. Geometric growth makes amortized append O(1). Total cost over $n$ appends is bounded by $3n$ because the geometric series $1 + 2 + 4 + \cdots + 2^k < 2 \cdot 2^k \le 2n$ sums to less than $2n$. The choice of factor (1.5 or 2) is a memory-vs-latency knob, not a complexity one.

In the next section we'll examine Memory Allocation Strategies in depth — exactly how and where the runtime gets these contiguous blocks, and why malloc isn't actually free.

Exercises

Conceptual

1. A dynamic array starts empty with capacity 1 and uses doubling. After 17 appends, what are the values of $n$, $c$, and the total number of writes performed (including resize copies)?
2. Prove that any growth factor $\alpha > 1$ gives amortized $O(1)$ append. Where does the proof break for $\alpha = 1$?
3. Why does Python's list use a growth pattern of roughly 1.125x with constant slop, instead of 2x? Hint: think about typical Python program memory pressure vs C++ program memory pressure.

Implementation

1. Extend the DynamicArray class above with insert(k, obj), pop(), and __setitem__. What is the worst-case complexity of each?
2. Add automatic shrinking: when $n \le c/4$, halve the capacity. Why $c/4$ and not $c/2$? (Hint: the wrong threshold causes $O(n)$ amortized behavior on a pathological alternating pattern.)
3. Implement pop_front. Then implement a circular-buffer version that runs in $O(1)$ amortized.

Analysis

1. Suppose the growth factor is 1.5. Prove that $n$ appends cost at most $4n$ total writes. Then redo the argument for factor $\alpha$ in general — express the bound as a function of $\alpha$.
2. A user calls append exactly $N$ times, starting from capacity 1 with doubling. How many times does the backing buffer get reallocated? Express your answer in terms of $N$.

Challenge

1. Design a data structure that supports both append and prepend in amortized $O(1)$, plus $O(1)$ random access. (Hint: two stacks, or a circular buffer.) How does the constant factor compare to a plain dynamic array?
2. Most implementations use a single backing array. Investigate the tiered-vector structure: an array of $\sqrt{n}$ arrays of size $\sqrt{n}$. What complexities does it offer for append, prepend, insert, and access? Why is it not the default?