· Development

Why appending to a dynamic array is O(1): capacity, growth and amortized time

Append sometimes copies the whole array, yet it counts as O(1). Capacity, amortized cost, what the Java, C++, Rust and Go docs promise, and reserving space.

DevelopmentAlgorithmsData structures

Python’s list.append, Java’s ArrayList.add, C++’s vector::push_back and Rust’s Vec::push are usually described as O(1): adding one element to the end takes constant time. Yet each of them keeps its elements in one contiguous array, and when that array is full it obtains more storage. That may require a new array and moving every stored value across. In Python and Java the array holds references to objects, not the objects themselves, so what moves is the references. Moving n values now and then still counts as O(1) because the O(1) is amortized.

Size and capacity

A dynamic array tracks two numbers: how many elements it holds (its size or length) and how many it can hold without reallocating (its capacity). The Java ArrayList documentation describes capacity as the size of the array used to store the elements and says it is always at least as large as the list size.

While size is below capacity, an append writes into a free slot and that’s it. When size equals capacity, the container must grow its storage and may allocate a new array and move the values. Rust’s Vec::push documentation says a push that reallocates takes O(capacity) time.

Where amortized O(1) comes from

Start with an empty array and double the capacity each time it fills. Copies happen when it fills at 1, 2, 4, 8, … elements, so over n appends the number of values moved is 1 + 2 + 4 + …, which stays below 2n. The total cost is proportional to n, so the average cost per append is constant. That average doesn’t assume random input. It says that n appends starting from an empty array cost time proportional to n, whatever you append. If you start counting from a large array that is already full, the very first append can be expensive, so the bound is stated from empty.

The growth rule matters. If the rule guarantees progress, as in max(1, ceil(r × old capacity)), and a fixed r is greater than 1, the copies form a geometric series whose sum is proportional to n. One example is r = 1.5. Adding a fixed 10 slots each time makes the copying proportional to n² instead. Counting one million appends into an empty array with the code below gives 1,048,575 copies (21 allocation or growth events, including the initial allocation) for doubling and 49,999,500,000 copies (100,000 allocation or growth events) for +10.

def count_copies(n, grow):
    cap = size = copies = 0
    for _ in range(n):
        if size == cap:
            copies += size
            cap = grow(cap)
        size += 1
    return copies

count_copies(10**6, lambda c: max(1, c * 2))  # 1048575
count_copies(10**6, lambda c: c + 10)         # 49999500000

What the documentation guarantees and what implementations choose

Official docs and specifications mostly promise the outcome and leave the growth factor open.

  • Java ArrayList: the growth policy isn’t specified beyond the fact that adding an element has constant amortized time cost.
  • C++ public working draft: operations such as push_back on vector must be implemented to take amortized constant time. No growth factor is given.
  • Rust Vec: no particular growth strategy is guaranteed, but whatever strategy is used guarantees amortized O(1) push.
  • Go specification: if capacity is too small, append allocates a new, sufficiently large underlying array. That’s all it says.

The actual factor is up to the implementation. When you append one element at a time, CPython 3.13’s list_resize adds an eighth of the new size plus 6 and rounds to a multiple of 4. The source comment gives the growth pattern 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, …. When a single call grows the list by a lot, as extend can, and the new size lands closer to that figure than to the old size, it skips the extra room and rounds the new size up to a multiple of 4. In the default GIL-enabled build, CPython resizes with realloc, so if the allocator can grow the block in place, nothing is copied. A free-threaded build allocates a new array and copies. OpenJDK 21’s ArrayList passes half the old capacity as its preferred growth, so appending one at a time grows the capacity by about 1.5× at ordinary sizes. Both are internal details that can change between versions, so code shouldn’t rely on these numbers.

Limits of amortized O(1)

Amortized O(1) doesn’t mean every call is fast. When growth allocates new storage and copies or moves the stored values, the operation can take time proportional to the number of elements. Code that cares about worst-case latency can therefore see occasional spikes.

Growth that allocates new storage also moves the elements. The C++ draft says reallocation invalidates all references, pointers and iterators to the elements. In Go, append reuses the underlying array when capacity allows and allocates a new one when it doesn’t, so you have to use the slice it returns.

When you know the count in advance

If you know roughly how many elements are coming, reserve capacity first and you’ll reallocate less. C++ has reserve, Java has ensureCapacity, and Rust has with_capacity and reserve. The guarantees differ. The C++ draft promises no reallocation during insertions after reserve until the size would exceed capacity, while the Java documentation only says ensureCapacity may reduce the amount of incremental reallocation.

For another look at what standard libraries do and don’t promise, see stable sorting.

Specifications and documentation used

Back to the blog