Dynamic Arrays & Amortized O(1) Append Explained

A dynamic array is an array that grows automatically as you add elements, so you never have to fix its length in advance. Under the hood it stores items in a fixed block of contiguous memory and quietly allocates a bigger block when it runs out of room. This page explains how that resizing works and why appending is amortized O(1) — fast on average even though an occasional append is expensive.

Every language in this course ships a dynamic array: C++ std::vector, Java ArrayList, JavaScript Array, and Python list.

Capacity vs size

A dynamic array tracks two numbers:

• Size — how many elements you have actually stored.
• Capacity — how many elements the current memory block can hold before it must grow.

When size == capacity and you append one more, the array allocates a larger block (typically double the capacity), copies the existing elements over, and adds the new one. Most appends just write into spare capacity in O(1); only the rare resize costs O(n).

#include <vector>
#include <iostream>

int main() {
    std::vector<int> a;
    std::cout << a.size() << " " << a.capacity() << "\n"; // 0 0
    for (int i = 0; i < 5; i++) a.push_back(i);
    std::cout << a.size() << " " << a.capacity() << "\n"; // 5, >=5
}

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> a = new ArrayList<>();
        for (int i = 0; i < 5; i++) a.add(i); // grows as needed
        System.out.println(a.size()); // 5
    }
}

const a = [];
for (let i = 0; i < 5; i++) a.push(i); // grows automatically
console.log(a.length); // 5

a = []
for i in range(5):
    a.append(i)  # grows automatically
print(len(a))  # 5

Why doubling gives amortized O(1)

The trick is geometric growth: each resize doubles capacity instead of adding a constant amount. Suppose you append n elements starting from an empty array. The copies happen at sizes 1, 2, 4, 8, … up to n. Their total cost is:

1 + 2 + 4 + ... + n  <  2n

That whole sequence of n appends costs under 2n operations, so the average per append is O(1) — this average over a sequence of operations is what “amortized” means.

Going deeper: If the array grew by a fixed step (say +1 each time) instead of doubling, you would copy on every append, giving 1 + 2 + … + n ≈ n²/2 total — that is O(n) per append. Geometric growth is what makes the amortization work.

For beginners: “Amortized O(1)” does not mean every append is fast. It means the slow ones are rare enough that the long-run average is constant. Compare with Big-O notation.

Reserve capacity when you know the size

If you know roughly how many elements you’ll add, pre-allocating avoids repeated resizes entirely:

std::vector<int> a;
a.reserve(1000);          // one allocation, no regrowth
for (int i = 0; i < 1000; i++) a.push_back(i);

ArrayList<Integer> a = new ArrayList<>(1000); // initial capacity
for (int i = 0; i < 1000; i++) a.add(i);

// JS arrays auto-manage capacity; you can hint a length:
const a = new Array(1000);
for (let i = 0; i < 1000; i++) a[i] = i;

# Python lists auto-manage capacity; a comprehension is idiomatic:
a = [i for i in range(1000)]

Cost summary

The space overhead is O(n): a dynamic array may hold up to roughly 2× the memory it strictly needs, the price you pay for cheap appends.

When to use a dynamic array

Reach for a dynamic array as your default sequence: fast index access, cheap appends, and cache-friendly contiguous storage. If you need frequent inserts or deletes in the middle, a linked list avoids the shifting cost. For the day-to-day operations on arrays, see array operations; to practice, try the array exercises.