Arrays & Dynamic Arrays

An array is a block of contiguous memory holding equally-sized elements. That one property gives it everything else: because element i lives at base + i × element_size, indexing is a single multiply-and-add — genuinely $O(1)$, with no search involved.

It is also the reason arrays are the default choice far more often than their complexity table suggests. Contiguity is exactly what the memory hierarchy is built to reward.

Core Concepts

Term	Meaning
Static array	Fixed capacity, decided at creation. C's int a[100].
Dynamic array	Grows as needed by reallocating. Python list, C++ std::vector, Go slice.
Capacity vs. size	Capacity is how many elements fit before reallocating; size is how many are actually stored.
Row-major / column-major	For 2-D arrays, whether consecutive memory holds a row or a column. C and Python are row-major; Fortran and MATLAB are column-major.

Mechanism

Why indexing is $O(1)$

int array of 4-byte elements, base address 0x1000

index:      0        1        2        3        4
address: 0x1000   0x1004   0x1008   0x100C   0x1010
              └── address = 0x1000 + index × 4 ──┘

No traversal, no comparison — arithmetic. This also means an array must know its element size at compile time, which is why an array of objects in most managed languages is really an array of references, with the objects themselves scattered across the heap.

Growth: how a dynamic array stays amortized $O(1)$

Appending is cheap until capacity is exhausted, at which point the whole buffer is reallocated and copied:

Python

# doc:no-run
# Conceptually, what append does
def append(self, value):
    if self.size == self.capacity:
        self.capacity = max(1, self.capacity * 2)   # the factor matters
        new_buffer = allocate(self.capacity)
        copy(self.buffer, new_buffer, self.size)    # O(n), but rare
        self.buffer = new_buffer
    self.buffer[self.size] = value
    self.size += 1

C++

// doc:no-run
// Conceptually, what push_back does
void push_back(const T& value) {
    if (size_ == capacity_) {
        capacity_ = std::max<std::size_t>(1, capacity_ * 2);    // the factor matters
        T* new_buffer = allocate(capacity_);
        std::uninitialized_move_n(buffer_, size_, new_buffer);  // O(n), but rare
        deallocate(buffer_);
        buffer_ = new_buffer;
    }
    buffer_[size_] = value;
    ++size_;
}

Doubling means resizes happen at sizes 1, 2, 4, 8, …, n, copying fewer than 2n elements in total across n appends — $O(1)$ amortized, in the sense developed in full in Amortized Analysis (the accounting-method argument there charges each append a constant number of prepaid "credits", enough to cover its own eventual share of a future copy). Growing by a fixed amount instead (say +10 each time) makes resizes just as frequent as the array grows, giving $O(n)$ amortized per append.

Language	Growth factor
C++ std::vector (libstdc++, libc++)	2×
Python list	~1.125× plus a constant (a gentler curve, tuned for memory)
Go slices	2× while small, tapering toward 1.25× for large slices

Why not always 2×?

A growth factor of 2 can never reuse the memory it previously freed — the sum of all earlier blocks is always just short of the next request. Factors below the golden ratio (~1.618) eventually allow the allocator to reuse that freed space, which is the argument for 1.5×. It is a memory-fragmentation trade, not a speed one.

Insert and delete: the shifting cost, traced

Indexing is $O(1)$, but inserting or deleting anywhere except the end means every element after the gap has to move, which is $O(n)$ worst case (and average case, since the expected number of elements shifted is proportional to n regardless of where the operation lands). Traced on [5, 1, 8, 3]:

start                    [5, 1, 8, 3]

insert 9 at front        [9, 5, 1, 8, 3]
  every existing element shifts one slot right to make room at index 0 — O(n) worst case

insert 7 at back         [9, 5, 1, 8, 3, 7]
  no shift needed, only a write past the last element — O(1) amortized (a resize may be due)

delete at index 1 (5)    [9, 1, 8, 3, 7]
  elements at index 2..5 (1, 8, 3, 7) each shift one slot left to close the gap — O(n) worst case

Only the back is cheap. Inserting or deleting at the front or in the middle always touches every element between the operation and the far end — there is no way to avoid the shift without changing representation (a linked list trades this shift for pointer-chasing instead).

The trace above is not just an illustration — it is exactly what the standard library does:

Python

arr = [5, 1, 8, 3]
arr.insert(0, 9)                  # insert at front — O(n) worst case: shifts every element right
assert arr == [9, 5, 1, 8, 3]
arr.append(7)                     # insert at back — O(1) amortized: no shift
assert arr == [9, 5, 1, 8, 3, 7]
del arr[1]                        # delete at index 1 — O(n) worst case: shifts elements left
assert arr == [9, 1, 8, 3, 7]

C++

#include <cassert>
#include <cstddef>
#include <vector>

void trace_shifts() {
    std::vector<int> arr{5, 1, 8, 3};
    arr.insert(arr.begin(), 9);          // insert at front — O(n) worst case: shifts right
    assert((arr == std::vector<int>{9, 5, 1, 8, 3}));
    arr.push_back(7);                    // insert at back — O(1) amortized: no shift
    assert((arr == std::vector<int>{9, 5, 1, 8, 3, 7}));
    arr.erase(arr.begin() + 1);          // delete at index 1 — O(n) worst case: shifts left
    assert((arr == std::vector<int>{9, 1, 8, 3, 7}));
}

Practical Usage

Python

# doc:no-run
# Reserve capacity when the final size is known — avoids repeated reallocation
result = [None] * n          # Python: allocate once
# C++: v.reserve(n);   Go: make([]int, 0, n)

# Iterate in memory order. This nesting is right for row-major languages:
for row in range(rows):
    for col in range(cols):
        total += matrix[row][col]      # consecutive addresses

# Reversing the loops touches memory with a stride of `cols` elements,
# wasting most of every cache line fetched — often several times slower
# on large matrices for identical arithmetic.

C++

// doc:no-run
// Reserve capacity when the final size is known — avoids repeated reallocation
std::vector<int> result;
result.reserve(n);              // one allocation; no reallocation while filling

// Iterate in memory order. This nesting is right for row-major layouts:
for (std::size_t row = 0; row < rows; ++row)
    for (std::size_t col = 0; col < cols; ++col)
        total += matrix[row][col];      // consecutive addresses

// Reversing the loops touches memory with a stride of `cols` elements,
// wasting most of every cache line fetched — often several times slower
// on large matrices for identical arithmetic.

Removing from the middle of an array is $O(n)$ because everything after the gap shifts down. When order does not matter, swapping the last element into the hole makes it $O(1)$:

Python

def remove_unordered(items, i):
    items[i] = items[-1]     # overwrite the hole with the last element
    items.pop()              # then drop the (now duplicated) tail

items = [10, 20, 30, 40]
remove_unordered(items, 1)
assert items == [10, 40, 30]     # order changed, but O(1) instead of O(n)

C++

void remove_unordered(std::vector<int>& items, std::size_t i) {
    items[i] = items.back();    // overwrite the hole with the last element
    items.pop_back();           // then drop the (now duplicated) tail
}

Edge Cases & Pitfalls

Holding a pointer across a growth is a use-after-free

In C++, any operation that may reallocate a vector — push_back, insert, resize — invalidates every pointer, reference and iterator into it. The classic bug:

// doc:no-run
std::vector<int> v = {1, 2, 3};
int& first = v[0];
v.push_back(4);        // may reallocate; `first` now dangles
first = 99;            // undefined behaviour

Python is safe from this specific fault because its elements are references and the GC tracks them, but the equivalent logical bug — caching an index that a later removal invalidates — survives in every language.

• Two-dimensional does not mean contiguous. int** in C, or a Python list of lists, is an array of pointers to separately-allocated rows. Only a true int[N][M] (or NumPy array) is one flat block, and only that one gets the cache behaviour described above.
• Insertion at the front is $O(n)$ for a dynamic array. If you need it often, use a deque, not a list.
• list.pop(0) in Python is $O(n)$, and inside a loop it silently turns a linear algorithm quadratic — collections.deque.popleft() is the $O(1)$ form.

Comparisons

	Array	Linked list
Index access	$O(1)$	$O(n)$
Insert/delete at a known position	$O(n)$	$O(1)$
Memory per element	Element only	Element + one or two pointers
Locality	Contiguous — prefetches perfectly	Scattered — a cache miss per node
Realistic verdict	The default	Only when splicing dominates and you already hold the node

Recall

InvariantElements sit at base + index × element_size, so access by index is arithmetic, never search.

Costs

index access (worst)$O(1)$

append at the end (amortized)$O(1)$

insert/delete at front or middle (worst)$O(n)$

search for an arbitrary value (worst)$O(n)$

Reach for itYou index by position or iterate in order, and appends happen mostly at the end.

TrapAssuming append is $O(1)$ worst case rather than amortized — the occasional resize is a real $O(n)$ pause, and holding a pointer/reference across a push_back in C++ is a use-after-free the moment that resize happens.

References

• Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, Ch. 16 — amortized analysis, including the table-doubling argument in full.
• CPython list implementation notes — the actual over-allocation formula, in the source.

Books & Videos

• Sedgewick & Wayne, Algorithms, 4th ed., §1.3 — resizing arrays and the amortized cost analysis.

Related Pages

• Linked Lists — the contrasting layout, and when it actually wins.
• Common Complexities — where the amortized-$O(1)$ argument is developed.
• CPU Caches — why contiguity is worth so much more than the operation counts imply.