Dynamic Arrays & Vector Growth Strategies

A dynamic array is a resizable array built on top of fixed-size contiguous memory. It keeps two numbers:

• size — how many elements are actually stored.
• capacity — how many elements the currently allocated block can hold (capacity ≥ size).

As long as size < capacity, appending is trivial: write to the next slot and increment size — O(1). The interesting case is when size == capacity and another element arrives: there is no room, so the array must reallocate and grow.

This is exactly the structure behind C++ std::vector, Java ArrayList, Python list, and Go slices. They give you the fast random access of an array with the convenience of unbounded growth.

Scenario: a dynamic array has size 8 and capacity 8 (completely full). One more element is inserted. What happens?

Because size == capacity, there is no free slot. The array performs a reallocation:

Key consequences:

• This single insertion costs O(n) — it copied 8 elements — versus O(1) for a normal append.
• Element addresses change: everything moved to a new block, so any old pointers / references / iterators into the vector are invalidated (a classic C++ bug source).
• The new capacity (16) leaves 7 empty slots, so the next 7 appends are all cheap O(1) — no reallocation until size reaches 16.

The growth factor (here ×2) is a deliberate design choice, and it is what the rest of this topic is about.

It is tempting to say "append is O(n) because it might copy everything." That statement confuses the worst single append with the typical one.

Claim to evaluate: "Vector insertion is always O(n) because resizing copies all elements." Do you agree?

No — this is wrong. The mistake is assuming a resize happens on every insertion. It does not: with doubling, a resize happens only when the size hits a power of two. To grow to n elements, the array reallocates at sizes 1, 2, 4, 8, …, n, and the total copying across all those resizes is a geometric series:

So most appends are O(1); only a vanishing fraction (one per doubling, i.e. O(log n) of them) trigger a copy, and even those are fully paid for by the cheap ones. The correct statement is: worst-case single append = O(n), but amortized append = O(1) — proven by the aggregate, accounting, and potential methods in the previous topics. The claim is true only about a rare individual operation, false as a description of overall performance.

When a vector grows, it multiplies its capacity by a growth factor. The two common choices are ×2 (doubling) and ×1.5. Both keep append amortized O(1) (any factor > 1 does — the copies still form a converging geometric series), but they trade off differently.

The theory is the same; the constants differ. The choice is a memory-vs-time engineering decision, examined next.

Doubling vs. 1.5× in terms of wasted memory.

Wasted memory = capacity − size (allocated slots not yet used). Right after a growth, a vector holding s elements has:

So doubling can waste up to ~2× the memory of the 1.5× strategy in the worst moment (just after growing). For a vector of a million large objects, doubling may hold a million empty slots; 1.5× holds only ~half a million. 1.5× is the more memory-frugal strategy.

There is a second, subtler memory point in doubling's disfavour: with ×2, the new block (2s) is always larger than the sum of all previously freed blocks (1 + 2 + … + s = 2s − 1 < 2s). The allocator can therefore never reuse the freed blocks to satisfy the next growth — memory keeps marching forward. A growth factor below the golden ratio (~1.618), such as 1.5, eventually lets freed blocks be recycled, easing fragmentation. This is precisely why MSVC and folly chose 1.5×.

Doubling vs. 1.5× in terms of how often reallocation happens.

Both strategies reallocate only O(log n) times over n appends, but with different bases and constants:

For example, to grow to 1,000,000 elements:

Doubling reallocates less often (~20 vs ~34 here), so it does fewer expensive copy passes and typically gives faster append throughput. Each reallocation is a full O(n) copy, so fewer of them means less total copying work — doubling wins on speed.

The two strategies sit at opposite ends of a single trade-off:

How to choose:

• Pick doubling when speed matters most and memory is plentiful — the default in GCC/Clang libstdc++/libc++.
• Pick 1.5× when memory footprint and fragmentation matter most — MSVC and folly's choice.

Either way the headline guarantee is unchanged: append is amortized O(1). The growth factor only tunes the constant — trading a bit of speed for a bit of memory. And to squeeze out reallocation entirely when the final size is known, call reserve(n) up front so the vector allocates once.

Any growth factor > 1 yields amortized O(1) append; ×2 minimizes reallocations, ×1.5 minimizes wasted memory — the fundamental cost–benefit trade-off of dynamic-array design.