Arrays & Dynamic Arrays: How They Work, Complexity, and When to Use Them

In plain words — the parking garage analogy

A multi-story parking garage numbers every space sequentially from 001 to 500. Given a ticket number, the attendant computes the floor and row in a second and walks straight to the car. They don't scan every space — they calculate. That's an array: every slot has a known, computable address, so access is instant regardless of size. The trade-off: the garage has a fixed layout. Adding a new row means tearing out walls (resizing), and sliding car #200 to the right to make room for a new one in spot #50 means moving everything in between.

What an array is, at the memory level

A static array is a fixed-size block of contiguous memory holding elements of the same size. If an array of 32-bit integers starts at memory address 1000, element 0 lives at 1000, element 1 at 1004, element 2 at 1008, and element i at 1000 + 4i. That formula is the array's superpower: to read element 5,000,000 the computer doesn't touch elements 0 through 4,999,999 — it computes one address and reads it. This is random access, and it's O(1).

Static array of 32-bit ints, base address = 1000

Index:    [  0  ] [  1  ] [  2  ] [  3  ] [  4  ]
Address:  1000    1004    1008    1012    1016
          ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐
Values:   │  42 │ │  17 │ │   8 │ │  99 │ │   3 │
          └─────┘ └─────┘ └─────┘ └─────┘ └─────┘

Access arr[3]:
  address = base + index × element_size
           = 1000 + 3   × 4
           = 1012        ← one arithmetic op, no loop
  Read memory at 1012 → 99 ✓

Contiguity has a second, quieter superpower: cache friendliness. CPUs pull memory in chunks (cache lines, typically 64 bytes), so when you read element i, elements i+1, i+2, … often arrive for free. Scanning an array is therefore fast not just in Big-O terms but in real-machine terms — often 10–100× faster than scanning a linked list of the same length, even though both are 'O(n)'. Big-O ignores constants; hardware does not.

The cost of contiguity: insertion and deletion

The same rigidity that makes indexing instant makes middle modifications expensive. To insert a value at index 2 of a 10-element array, every element from index 2 onward must shift right by one slot — there is no gap to slip into. Deleting from the middle shifts everything after it left. Both are O(n) in the worst case (inserting at the front shifts all n elements). Operations at the end are the exception: nothing needs shifting, so appending to a non-full array and removing the last element are O(1).

Insert value 55 at index 2 in a 5-element array

BEFORE:
  [0]  [1]  [2]  [3]  [4]  [5] ← empty slot
   10   20   30   40   50

Step 1: shift elements 2..4 right by 1 (right to left to avoid overwrite)
  [0]  [1]  [2]  [3]  [4]  [5]
   10   20    ?   30   40   50

Step 2: shift [3]→[4] (already done), [2]→[3]:
  [0]  [1]  [2]  [3]  [4]  [5]
   10   20    ?   30   40   50   ← 3 shifts for 3 elements after index 2

Step 3: write 55 at index 2
  [0]  [1]  [2]  [3]  [4]  [5]
   10   20   55   30   40   50  ✓

Cost: proportional to (n - insertionIndex) shifts → O(n) worst case (insert at front)

Dynamic arrays: growing on demand

Static arrays have a fixed capacity chosen up front, which real programs rarely know. The fix is the dynamic array (the resizable list type in essentially every modern language): a static array plus two numbers — size (elements in use) and capacity (slots allocated). Appends fill spare capacity in O(1). When size hits capacity, the structure allocates a new array of double the capacity, copies all elements over, and frees the old one.

Dynamic array growth — appending 1 through 8

After append(1):  capacity=1, size=1
  [ 1 ]

After append(2):  FULL → resize to capacity=2, copy, then append
  [ 1 | 2 ]

After append(3):  FULL → resize to capacity=4, copy, then append
  [ 1 | 2 | 3 |   ]   (one spare slot)

After append(4):  fits in spare slot
  [ 1 | 2 | 3 | 4 ]

After append(5):  FULL → resize to capacity=8, copy, then append
  [ 1 | 2 | 3 | 4 | 5 |   |   |   ]   (three spare slots)

After append(6,7,8): fill spare slots, no resize
  [ 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 ]

Resize events: at sizes 1, 2, 4 → copies: 1+2+4 = 7 for 8 appends ≈ O(1) each

Why doubling gives amortized O(1) append

That copy step is O(n) — so how can append be called O(1)? Because doubling makes resizes geometrically rare. Starting from capacity 1 and appending n items, you copy at sizes 1, 2, 4, 8, … up to n. The total copies are 1 + 2 + 4 + … + n ≈ 2n, which is O(n) copy-work spread across n appends — O(1) amortized per append, exactly the concept from Lesson 2. Growing by a fixed amount instead (say +10 slots each time) would trigger resizes every 10 appends and cost O(n²) total; the multiplicative growth factor is the entire trick.

Core operations — pseudocode and invariants

class DynamicArray:
    data     ← static array of capacity slots
    size     ← 0        # elements in use
    capacity ← 1        # slots allocated

    append(x):
        if size == capacity:
            newData ← new array of size capacity * 2
            copy data[0..size-1] into newData
            data     ← newData
            capacity ← capacity * 2
        data[size] ← x
        size ← size + 1
        # Invariant: size ≤ capacity always

    get(i):
        assert 0 ≤ i < size          # bounds check
        return data[i]               # O(1)

    set(i, x):
        assert 0 ≤ i < size
        data[i] ← x                  # O(1)

    insert(i, x):
        ensure capacity (resize if full)
        for j from size-1 downto i:  # shift right, back to front
            data[j+1] ← data[j]
        data[i] ← x
        size ← size + 1
        # Cost: O(size - i) — worst case O(n) at front

    delete(i):
        for j from i to size-2:      # shift left
            data[j] ← data[j+1]
        size ← size - 1
        # Optionally shrink: if size < capacity/4 → halve capacity
        # Use capacity/4 threshold (not capacity/2) to prevent thrashing

Full complexity table

Worked example: tracing five appends step by step

Append 1, 2, 3, 4, 5 into a dynamic array starting at capacity 1:

Total copies: 1 + 2 + 4 = 7, for 5 appends. That's 1.4 copies per append — and the ratio approaches 2 as n grows, converging to O(1) amortized.

Common pitfalls

• Inserting or deleting at the front in a loop. Each operation shifts the whole array — n front-insertions cost O(n²). If you need cheap operations at both ends, use a deque.
• Deleting elements while iterating forward. Deletion shifts later elements left, so the iterator skips the element after every deleted one. Iterate backwards, or build a new filtered array.
• Off-by-one bounds. Valid indices are 0 through size − 1. The last element is at size − 1, and loops should run while i < size, not i ≤ size.
• Forgetting that 'contains' is O(n). Membership tests on an unsorted array scan everything. Doing one inside a loop silently creates O(n²); a hash set fixes it.
• Assuming worst-case O(1) append. A single append can stall on a resize. In latency-critical code, pre-allocating capacity up front avoids mid-stream resize pauses entirely — and it's a one-line optimization.
• Treating shrinking as free. If you implement a shrink-on-delete policy, use the capacity/4 threshold — not capacity/2 — to avoid the oscillation bug: fill to capacity, trigger resize to 2n, then delete one element and trigger shrink back to n, then append and trigger resize again — each of those is O(n).

When to use an array — and when not to

• Use it as your default collection: fast indexed access, fast iteration, compact memory, cheap appends. Most problems need nothing more.
• Use it when data is sorted or sortable — arrays unlock binary search and the two-pointer patterns.
• Use it as the backbone of other structures — heaps, hash tables, and adjacency lists all use arrays underneath.
• Avoid it when you insert/delete heavily at the front or middle of large collections — that's linked-list or deque territory.
• Avoid it as a lookup table by arbitrary key — that's what hash tables are for. Arrays index by position, not by meaning.

Variations worth knowing

• Circular buffer (ring buffer). A fixed-size array where head and tail indices wrap around modulo capacity. Gives O(1) enqueue and dequeue — the foundation of most queue implementations. Queues lesson covers this in detail.
• 2D array. A row-major or column-major grid: a 1D array where element [row][col] is at base + (row × cols + col) × element_size. Row-major access (scanning left to right across a row) is cache-friendly; column-major access on a row-major array is not — a real performance concern for large matrix algorithms.
• Bit array (bitset). An array where each element is a single bit, packed 64 per word. Used for dense membership sets and the Sieve of Eratosthenes.

Practice problems

1. Rotate array. Given an array of n elements, rotate it right by k positions in O(n) time and O(1) extra space. Hint: reverse the whole array, then reverse the first k and the last n-k subarrays.
2. Remove duplicates in-place. Given a sorted array, remove duplicates so each value appears once, returning the new length. Do it in O(n) time and O(1) space (the standard two-pointer approach).
3. Dynamic array from scratch. Implement a resizing array in your language without using the built-in list type. Include get, set, append, insert, delete, and a size property. Track resize events — confirm you see O(log n) of them for n appends.

Key takeaways

• An array is contiguous memory; indexing is one address computation, hence O(1).
• Contiguity makes iteration cache-fast but middle insertion/deletion O(n) due to shifting.
• Dynamic arrays add size/capacity bookkeeping and double on overflow, giving amortized O(1) append at the cost of up to ~2× memory slack.
• Doubling (multiplicative growth) is essential — additive growth degrades total appends to O(n²).
• Arrays are the default structure; reach for something else only when their specific weaknesses (front/middle churn, key-based lookup) are your hot path.

Next: the array's text-shaped sibling — strings and string algorithms. To drill array complexity until it's automatic, quiz yourself in the **AI Learning app**.

AI Learning: AI/ML/DS Q&A

A private, offline app to learn Artificial Intelligence, Machine Learning & Data Science at your own level: ~10,000 Q&A, illustrated guides, cheat sheets, quizzes and mock tests.

Coming soon toGoogle Play