Why Are Arrays O(1) Access but O(n) Insert and Delete?

Contiguous arrays are fundamental data structures in classical computing because they store elements in adjacent memory locations. This physical layout allows the processor to calculate the exact memory address of any element instantly, resulting in constant time random access. However, this same requirement for adjacency forces the system to shift surrounding elements whenever an item is added or removed, leading to linear time complexity for insertions and deletions.

Memory Layout and \(O(1)\) Random Access

In classical computing, system memory (RAM) can be visualized as a long, continuous sequence of bytes, each with a unique numerical address. When a contiguous array is allocated, the operating system reserves a single, unbroken block of these memory addresses.

Because every element in the array has the same data type and occupies the exact same number of bytes, the memory address of any element at index \(i\) can be computed using a simple arithmetic formula:

\[\text{address}(i) = \text{base\_address} + (i \times \text{element\_size})\]

Here, \(\text{base\_address}\) is the memory location of the first element (index \(0\)), and \(\text{element\_size}\) is the size of a single element in bytes. Since multiplication and addition take a fixed number of CPU cycles regardless of how large the array is, accessing any element by its index takes \(O(1)\) constant time.

The Cost of \(O(n)\) Insertion and Deletion

While contiguous memory enables instant lookups, it creates a strict structural constraint: there can be no empty gaps between elements, and the order of elements must be preserved in physical memory.

Insertion

When inserting a new element at index \(i\) in an array of length \(n\):

  1. Every element currently at index \(i\) through \(n - 1\) must be shifted one position to the right to make room for the new value.
  2. In the worst-case scenario—inserting at the very beginning of the array (index \(0\))—all \(n\) elements must be moved.
  3. On average, inserting at a random position requires shifting \(\frac{n}{2}\) elements.

Because the number of operations scales directly with the number of elements \(n\), insertion has a time complexity of \(O(n)\).

Deletion

Deleting an element at index \(i\) follows the reverse process:

  1. Removing the element leaves an empty slot in the middle of the contiguous block.
  2. To maintain the contiguous property, every element from index \(i + 1\) through \(n - 1\) must be shifted one position to the left to fill the gap.
  3. Just like insertion, deleting from index \(0\) requires shifting \(n - 1\) elements, resulting in \(O(n)\) linear time complexity.

Hardware Cache Efficiency

Beyond the theoretical Big O notation, contiguous arrays are heavily favored in classical computing because of how modern CPUs handle memory. Processors use small, ultra-fast memory caches (L1, L2, and L3) to store recently accessed data. When the CPU reads an element from an array, it automatically loads a contiguous chunk of nearby memory—known as a cache line—into the cache. This spatial locality means that iterating through a contiguous array is significantly faster in practice than traversing non-contiguous structures like linked lists.