Back to 20 Concepts
memory • Intermediate
Dynamic Array Resizing & Amortized O(1) Complexity
Dynamic arrays (std::vector, ArrayList, Python list, JS Array) automatically double their backing storage capacity (2 -> 4 -> 8 -> 16) when full, reallocating memory and copying elements in amortized O(1) time.
Intuitive Mental Model
The Growing Family Home: Instead of moving house every time you buy 1 new shirt, you build a home with twice as many rooms as you currently need. Moving is expensive, but it happens so rarely that the cost per shirt is negligible.
C / TypeScript ImplementationHardware & Algorithmic Standard
// Dynamic Array Amortized Analysis (Geometric Doubling):
// Insertions: 1, 2, 3, 4, 5, 6, 7, 8
// Resizing Copies: 1 + 2 + 4 = 7 copies total for 8 insertions!
// Total Cost = N insertions + (2N - 1) copies <= 3N operations -> O(1) Amortized!
function push(element) {
if (this.size === this.capacity) {
this.resize(this.capacity * 2); // Double capacity
}
this.buffer[this.size++] = element;
}Key Architectural Takeaways
- •Amortized O(1): While a single insertion may take O(N) during reallocation, the average cost across N insertions is strictly O(1).
- •Geometric Doubling: Multiplying capacity by a constant factor (typically 1.5x or 2.0x) is required for amortized O(1); adding a fixed amount (+10) causes catastrophic O(N^2) total runtime.
Common Coding Mistake
Growing an array by a fixed constant size (e.g. capacity += 10), resulting in O(N^2) total copy overhead.
Optimal Solution
Always use geometric doubling (capacity *= 2) or preallocate capacity with vector.reserve(N).