# Why Dynamic array sizes are doubled in capacity? In systems programming, the dynamic array (e.g., `std::vector`, `ArrayList`, or Python's `list`) is a fundamental tool. But have you ever paused to ask why these containers **double** their capacity when they run out of space? It might feel like "**wasting**" memory, but the math reveals that doubling is the brilliant way to keep our most common operation `append()` performing at best speed. ## The Performance Killer : Linear Growth (\\(+K\\)) Suppose we decide to be "memory efficient" and grow our array by a fixed amount—say, **100 slots**—only when we absolutely need to. If we want to insert **N** elements, how many times do we have to copy data to a new memory location? * **Initial State:** You allocate a block of **100**. You fill it up (Elements 1 to 100). **Copies = 0.** * **The 101st Element:** You have no room. You must allocate a new block of **200**. You copy the **100** existing elements over. * **The 201st Element:** You are full again. You allocate a block of **300**. You copy the **200** existing elements over. * **The 301st Element:** You allocate **400**. You copy the **300** existing elements over. The total work (W) is an arithmetic progression: $$W = 100 + 200 + 300 + ... + (N - 100)$$ Factoring out the 100, $$W = 100 \times (1 + 2 + 3 + \dots + \frac{N}{100} - 1)$$ Applying the Arithmetic Series Formula, The sum of 1 to M is, The quadratic formula is \\(\frac{M(M+1)}{2}\\). Here, \\(M \approx \frac{N}{100}\\) $$W \approx 100 \times \frac{(\frac{N}{100})^2}{2}$$ Using the sum of an arithmetic series, this results in: $$W \approx 100 \times \frac{N^2}{100^2 \times 2} = 100 \times \frac{N^2}{10000 \times 2} = \frac{N^2}{100 \times 2} = \mathbf{\frac{N^2}{200}}$$ In Big-O terms, this is \\(O(N^2)\\) total work. If you divide that by **N** insertions, each individual `append()` costs \\(O(N)\\). As your dataset grows, your application will get exponentially slower. ## The Efficiency King: Geometric Growth(\\(\times 2\\)) Now let's look at the same \\(N\\) where we start with 100 slots, using the **Doubling** method: 1. **Initial State:** Allocate **100**. Fill them. **Copies = 0.** 2. **The 101st Element:** Double to **200**. Copy **100**. 3. **The 201st Element:** Double to **400**. Copy **200**. 4. **The 401st Element:** Double to **800**. Copy **400**. 5. **The 801st Element:** Double to **1600**. Copy **800**. For **N** elements (where N is a power of 2), our copy operations look like this: $$W = 100 \times (1 + 2 + 4 + 8 + \dots + \frac{N}{2}) = 100 \times (2^0 + 2^1 + 2^2 + 2^3 + \dots + 2^{k-1})$$ This is a **geometric series** where base is **2**. A key property of this series is that the sum of all previous terms is always less than the next term. Specifically: $$W \approx 100 \times \sum_{i=0}^{x} 2^i = 2^{x+1} - 1 \approx 100 \times \sum_{i=0}^{k-1} 2^i = 2^{k-1+1} - 1\approx 100 \times \sum_{i=0}^{k-1} 2^i = 2^{k} - 1$$ $$ W \approx 2^k \approx N-100$$ ### The Big Reveal: Amortized (\\(O(1)\\)) To find the average cost of a single `append`, we take the total work and divide it by the number of elements: $$\frac{Total\ Work}{Total\ Elements} = \frac{N - 1}{N} \approx 1$$ Even though some appends are "expensive" (the ones that trigger a resize), the vast majority are "cheap." On average, every append costs a constant amount of time, or as we call it in software world, \\(O(1)\\) ## Memory vs. Speed: The Growth Factor ($\\alpha$) While doubling \\(\alpha = 2\\) is the textbook standard, the specific multiplier can vary: * **Factor of 2.0:** Extremely fast, but because \\(1 + 2 + 4 < 8\\), the memory allocator can never "reuse" the old chunks of memory you just left behind. They are always too small for the next jump. * **Factor of 1.5:** Used by many modern libraries (like `libc++` or `FBVector`). Because \\(1.5\\) is smaller, it allows the allocator to eventually "recycle" the memory from previous steps, improving **cache locality** and reducing fragmentation.

Strategy

Total Copies (N)

Avg. Append Cost

Memory Overhead

Linear (+100)

\approx N ^2

O(N) ~ Slow

Low

Geometric ( \times 2 )

\approx N

O(1) ~ Fast

Up to 50%

* * * ### Final Thought We don't double the array because we are greedy for RAM; we double it because it turns a quadratic performance disaster into a linear, predictable success. It is one of the most successful "space-time tradeoffs" in computer science.