Array Operations and Complexity

The Operation Zoo

Every array data structure exposes the same handful of primitive operations — read by index, write by index, insert, delete, search, traverse, slice. Their asymptotic costs are deceptively simple to write down. Their real costs on a real machine, fighting cache lines and branch predictors, can differ by two orders of magnitude from what big-O suggests. A serious engineer owns both views.

This section walks every canonical operation, derives its tight bound, and then anchors the bound with hardware-level intuition. We end with the patterns that working engineers actually use to pick the right operation for the right job.

Random Access and Update: The O(1) Miracle

Random access — reading $A[i]$ for any valid $i$ in constant time — is the defining superpower of arrays. The reason is pure arithmetic:

$\mathrm{addr}(A[i]) \;=\; \mathrm{base} + i \cdot s$

where $\mathrm{base}$ is the start of the backing buffer and $s$ is the stride (size of one element in bytes). One multiply, one add, one load — three machine instructions, zero traversal. No matter how big the array is, the address calculation is the same width. That is where the$O(1)$ comes from. Update is symmetric: same address calculation, plus a single store.

Searching: Linear and Binary

A linear search examines elements one at a time. Best case the target is the first element ($O(1)$), worst case it is not there at all ($O(n)$), expected case for a uniformly random target position is$\approx n / 2$ probes — still$O(n)$ because constants disappear in asymptotic notation.

1def linear_search(arr, target):
2    for i, x in enumerate(arr):
3        if x == target:
4            return i        # found
5    return -1               # not found

If the array is sorted, binary search lets us discard half the remaining range with each comparison:$T(n) = T(n / 2) + O(1)$, which solves to$T(n) = O(\log n)$. We covered the invariant carefully in Chapter 3 §3 (Recurrences). The key trade is up front: you paid $O(n \log n)$ to sort once, and you now reap $O(\log n)$ on every query thereafter. For $q$ queries the total is$O(n \log n + q \log n)$ — far better than $O(qn)$ as soon as$q \gg \log n$.

Insertion and Deletion: Where the Cost Hides

The expensive operations on an array are the ones that change the array's shape. Insertion at index $k$requires shifting every element from $k$ to$n - 1$ one slot to the right to make room. That is $n - k$ writes. Worst case$k = 0$ (insert at the front) gives$O(n)$; best case $k = n$(insert at the end) is $O(1)$.

Deletion is the mirror: $n - k - 1$ elements slide left to close the hole, plus one drop at the tail.

arr=[7,3,9,4]  →  n=4

arr=[7,3,9,4]  →  arr=[7,3,9,4,None]

for k=1, n=4: i = 4, 3, 2

i=4: arr[4]=arr[3]=4 → [7,3,9,4,4]
i=3: arr[3]=arr[2]=9 → [7,3,9,9,4]
i=2: arr[2]=arr[1]=3 → [7,3,3,9,4]

arr[1]=99 → [7,99,3,9,4]

arr=[7,99,3,9,4], k=1  →  removed=99

i=1: arr[1]=arr[2]=3 → [7,3,3,9,4]
i=2: arr[2]=arr[3]=9 → [7,3,9,9,4]
i=3: arr[3]=arr[4]=4 → [7,3,9,4,4]

arr=[7,3,9,4,4] → arr=[7,3,9,4]

n=8, k=11  →  k=3

[1,2,3,4,5,6,7,8], k=3 → [3,2,1,4,5,6,7,8]

[3,2,1,4,5,6,7,8] → [3,2,1,8,7,6,5,4]

[3,2,1,8,7,6,5,4] → [4,5,6,7,8,1,2,3] ✓

1def insert_at(arr, k, v):
2    """Insert value v at index k. Returns nothing; mutates arr."""
3    n = len(arr)
4    arr.append(None)                # grow by 1 slot
5    for i in range(n, k, -1):       # walk from new tail down to k+1
6        arr[i] = arr[i - 1]         # shift each element right by 1
7    arr[k] = v                      # place new value
8
9def delete_at(arr, k):
10    """Delete element at index k. Returns the removed value."""
11    removed = arr[k]
12    n = len(arr)
13    for i in range(k, n - 1):       # walk from k up to second-last
14        arr[i] = arr[i + 1]         # shift each element left by 1
15    arr.pop()                       # drop the duplicated tail
16    return removed
17
18def rotate_left(arr, k):
19    """Rotate arr left by k positions, in place, in O(n) using 3 reverses."""
20    n = len(arr)
21    if n == 0:
22        return
23    k %= n
24    _reverse(arr, 0, k - 1)
25    _reverse(arr, k, n - 1)
26    _reverse(arr, 0, n - 1)
27
28def _reverse(arr, lo, hi):
29    while lo < hi:
30        arr[lo], arr[hi] = arr[hi], arr[lo]
31        lo += 1
32        hi -= 1

Direction of the shift loop matters. Insertion walks right-to-left. Deletion walks left-to-right. Reverse the direction and you overwrite values before reading them — one of the most common bugs in hand-rolled array code.

Amortized Append and the Resize Drama

Dynamic arrays advertise amortized$O(1)$ append, but each individual append can cost $O(n)$ when the underlying buffer is full and must be reallocated and copied to a larger one. The standard analysis (covered in detail in Ch 7) uses doubling: when the buffer fills, allocate $2n$ slots and copy.

The bookkeeping argument: across $n$ appends the total work for resizes is$1 + 2 + 4 + \cdots + n / 2 + n < 2n$. So$n$ appends cost$O(n)$ total &Rightarrow; per append is$O(1)$ averaged out, even though one unfortunate append paid $\Theta(n)$ for the copy that day.

Bulk Operations: Concat, Reverse, Rotate, Compare

Operations that must touch every element are inevitably$\Theta(n)$:

• Concatenate arrays of size$n$ and $m$:$O(n + m)$. Allocate one buffer of size$n + m$, copy both. Repeated concatenation inside a loop becomes $O(n^2)$ — the classic Python "build a string with +=" performance trap. Use $\texttt{''.join(parts)}$ instead.
• Reverse in place:$n / 2$ swaps via two pointers walking inward. $O(n)$, no extra space.
• Rotate left by k: the three-reverses trick achieves $O(n)$ time and$O(1)$ space — reverse$[0, k-1]$, reverse$[k, n-1]$, reverse the whole thing. We implement it in the code panel above.
• Equality compare: in the worst case (arrays differ only at the last index) you must read all$2n$ values — $O(n)$.
• Min / max / sum / mean / variance: a single linear pass — $O(n)$ — and trivially parallelizable.

Slicing: Copy or View?

The semantics of $A[i:j]$ change drastically between languages, and this single decision dominates real-world performance.

The same operation in C++ for comparison

a = [1,2,3,4,5], k=1
memmove copies 4 ints (3,4,5 + the 0 we appended)
a becomes [1, 1, 2, 3, 4]
then a[k]=v overwrites the slot

1#include <vector>
2#include <cstring>
3#include <chrono>
4#include <iostream>
5
6void insert_at(std::vector<int>& a, size_t k, int v) {
7    a.push_back(0);                                  // grow by 1
8    std::memmove(&a[k + 1], &a[k],                   // bulk shift right
9                 (a.size() - k - 1) * sizeof(int));  // (n - k) * 4 bytes
10    a[k] = v;
11}
12
13void delete_at(std::vector<int>& a, size_t k) {
14    std::memmove(&a[k], &a[k + 1],                   // bulk shift left
15                 (a.size() - k - 1) * sizeof(int));
16    a.pop_back();
17}
18
19int main() {
20    std::vector<int> a(1'000'000, 0);
21    auto t0 = std::chrono::high_resolution_clock::now();
22    insert_at(a, 0, 42);                             // worst case: shift 1M ints
23    auto t1 = std::chrono::high_resolution_clock::now();
24    std::cout << "front insert on n=1e6: "
25              << std::chrono::duration_cast<std::chrono::microseconds>(t1 - t0).count()
26              << " us\n";
27}

Interactive: Array Operation Animator

Pick an operation, drag the index $k$ slider and value $v$ slider, and click Run step. Amber cells indicate values that changed. Blue cells indicate cells that participated in a shift (read once, written once). The cells touched counter is the literal number of read / write events the operation just performed — the constant factor big-O hides. Compare an "Insert at front" against a "Swap-pop" on the same array and watch cumulative touches diverge.

Constants Matter: Cache Locality vs Big-O

Two operations that are both $O(1)$ can differ in real wall-clock cost by 50× or more. The reason is the memory hierarchy:

The bottom two rows are the same algorithm asymptotically, on the same size of input, with a 50–100× gap. Big-O is unbothered. Your latency budget is not.

Real-World Patterns

1. Game engines — entity arrays. Append-heavy, delete with swap-pop. Order does not matter; cache-friendly iteration is everything.
2. Audio processing — ring buffers. A pure dynamic array would prepend on every input sample ($O(n)$); a ring buffer makes it$O(1)$ by reusing slots.
3. Trading systems — sorted order books. Sorted array with binary search for price lookup, occasional inserts paid for once on every quote. At HFT scale these arrays are even replaced with cache-line-aligned, branchless variants.
4. Time-series databases (Druid, InfluxDB, ClickHouse).Append-only column arrays. Never delete or insert in the middle; all writes are tail-appends. Reads are sequential range scans. This pattern is the only reason these systems can ingest millions of points per second.
5. Compiler symbol tables. Small arrays of structs with linear search beat hash maps for$n < 16$ — cache locality wins over asymptotics at small sizes.
6. GPU vertex / index buffers. Append-only on the CPU side, then frozen and shipped to the GPU. No mid-array edits ever.
7. DOM child lists in browsers. When you call$\texttt{node.appendChild(c)}$ 10000 times in a tight loop, you pay the array shift cost plus a layout reflow per call. Hence the$\texttt{DocumentFragment}$ pattern: build off-tree, attach once.
8. Genomics — sequence arrays. A human genome is$3 \cdot 10^9$ bytes as an array of nucleotides. Random access by index is the only way tools like BWA / minimap2 are tractable. Insertions are forbidden; mutations are recorded as a separate diff structure.
9. UI virtualization. A list of 100,000 items cannot render every row. Materialize only the visible window into a small array, recycle DOM nodes — turn an$O(n)$ render into$O(\text{visible})$.
10. Database B-tree pages. Each page is a small sorted array of keys. Insert pays$O(\text{page size})$ shifts — tolerable because page size is bounded (typically 4–16 KB &Rightarrow; a few hundred keys).

Decision Rules: Which Operation, Which Structure?

Memorize these. They cover ~90% of array-related design decisions.

Heuristic: if the operation you run most often is$O(1)$ on an array, use an array. If the operation you run most often is $O(n)$ on an array and $n$ exceeds a few thousand, change structures — you are paying a tax that compounds.

The next two sections (Two Pointer and Sliding Window) are entirely about turning an apparent $O(n^2)$ algorithm on an array into $O(n)$ — using nothing but the operations we just catalogued.