Static vs Dynamic Arrays, Amortized O(1) Operations & Memory Locality

Beginner12 min read•Updated: Jul 11, 2026

Static vs Dynamic Arrays, Amortized O(1) Operations & Memory Locality

The Array is the most ubiquitous data structure in computer science. Arrays store elements in contiguous (sequential) memory locations, providing lightning-fast $O(1)$ constant-time random access via direct memory offset arithmetic.

1. Real-World Analogy: Hotel Rooms on a Floor

Imagine a luxury hotel with numbered rooms 100, 101, 102, 103... arranged sequentially along a straight corridor:

If you know Room 100 starts at memory address 0x1000 and each room is 4 meters wide, you can calculate the exact location of Room 105 instantly:

$$\text{Address} = \text{Base Address} + (\text{Index} \times \text{Size}) = 0x1000 + (5 \times 4) = 0x1014$$

You do not need to walk past rooms 101, 102, 103, and 104 to know where 105 is. This hardware math gives arrays $O(1)$ instant random access!

2. Static Arrays vs Dynamic (Resizing) Arrays

Static Arrays (e.g. C++, Java primitive arrays): Fixed capacity defined at declaration. Cannot grow or shrink once allocated in memory.
Dynamic Arrays (e.g. Python list, JavaScript Array, C++ std::vector, Java ArrayList): Automatically resize when capacity is reached.

How Dynamic Arrays Resize (The Doubling Strategy):

When you append to an array whose internal capacity is full:

1
Allocate a brand new array in memory with double the capacity ($2 \times \text{old size}$).
2
Copy all $n$ existing elements into the new memory space.
3
Deallocate the old array.
4
Append the new element.

Output

1Capacity: 4 [10, 20, 30, 40] (FULL)
2Append 50 triggers RESIZE:
31. Allocate new memory of capacity 8
42. Copy [10, 20, 30, 40]
53. Append [50] -> Capacity: 8 [10, 20, 30, 40, 50, _, _, _]

3. What is Amortized $O(1)$ Complexity?

While resizing copies $n$ elements and takes $O(n)$ time, resizing happens very infrequently (at powers of 2: $1, 2, 4, 8, 16, 32 \dots$).

If you append $n$ elements: $$\text{Total Copies} = 1 + 2 + 4 + 8 + \dots + n < 2n$$ Averaging $2n$ copying steps across $n$ operations yields: $$\frac{2n}{n} = 2 \text{ operations per append on average} \implies \mathbf{O(1)\text{ Amortized Time!}}$$

4. Hardware Cache Locality (Why Arrays Beat Linked Lists)

Modern CPUs fetch data from RAM in 64-byte Cache Lines rather than single bytes. Because array elements sit contiguously side-by-side in RAM, loading arr[0] into CPU L1 cache automatically loads arr[1], arr[2], and arr[3] simultaneously. This phenomenon is called Spatial Locality, making arrays up to 10x faster in practice than pointer-based data structures like Linked Lists.

5. Dual Code Implementation: Custom Resizing Dynamic Array

Python 3:

Python

1import ctypes
2 
3class DynamicArray:
  def __init__(self):
      self._size = 0
      self._capacity = 1
      self._array = self._make_array(self._capacity)
8 
  def __len__(self) -> int:
      return self._size
11 
  def __getitem__(self, index: int):
      if not 0 <= index < self._size:
          raise IndexError("Index out of bounds")
      return self._array[index]
16 
  def append(self, element) -> None:
      if self._size == self._capacity:
          self._resize(2 * self._capacity)
      self._array[self._size] = element
      self._size += 1
22 
  def _resize(self, new_capacity: int) -> None:
      new_array = self._make_array(new_capacity)
      for i in range(self._size):
          new_array[i] = self._array[i]
      self._array = new_array
      self._capacity = new_capacity
29 
  def _make_array(self, capacity: int):
      return (capacity * ctypes.py_object)()

Modern JavaScript / TypeScript:

TypeScript

1export class CustomDynamicArray<T> {
private data: (T | undefined)[];
private size: number = 0;
private capacity: number;
5 
constructor(initialCapacity: number = 2) {
  this.capacity = initialCapacity;
  this.data = new Array(this.capacity);
}
10 
public length(): number {
  return this.size;
}
14 
public get(index: number): T {
  if (index < 0 || index >= this.size) {
    throw new RangeError('Index out of bounds');
  }
  return this.data[index] as T;
}
21 
public push(element: T): void {
  if (this.size === this.capacity) {
    this.resize(this.capacity * 2);
  }
  this.data[this.size] = element;
  this.size++;
}
29 
private resize(newCapacity: number): void {
  const nextData = new Array(newCapacity);
  for (let i = 0; i < this.size; i++) {
    nextData[i] = this.data[i];
  }
  this.data = nextData;
  this.capacity = newCapacity;
}
38}

6. Big-O Complexity Comparison

Operation	Array Complexity	Reason
Lookup by Index (`arr[i]`)	$O(1)$	Direct memory offset calculation
Append to End	$O(1)$ Amortized	Occasional resize amortized over $n$ appends
Insert at Beginning (`unshift`)	$O(n)$	Every existing element must shift 1 index to the right
Delete from Beginning (`shift`)	$O(n)$	Every existing element must shift 1 index to the left
Search by Value (unsorted)	$O(n)$	Linear scan across all elements

Interactive Quiz• Knowledge Check

Multiple Choice Questions

Question 1

Why does accessing an element in an array by its index take constant $O(1)$ time?

Question 2

What is the time complexity of inserting or deleting an element at index 0 of an array containing $n$ elements?

Question 3

What does "Amortized $O(1)$" mean in the context of appending to a dynamic array?

Question 4

What computer hardware advantage makes sequential iteration over an array significantly faster than traversing a linked list?

Question 5

What happens if a program attempts to read arr[10] on an array allocated with size 5 in languages like C or C++?

Next Lesson

Two-Pointer Technique: Opposite-Direction & Fast-Slow Patterns

Continue learning with hands-on practice, examples, and exercises in the upcoming topic.

Related Lessons

Previous Lesson	Next Lesson
Space Complexity, Auxiliary Memory & Stack vs Heap Allocation	Two-Pointer Technique: Opposite-Direction & Fast-Slow Patterns

Practice Quiz

Test your understanding of this lesson with 5 questions. Each question has one correct answer.

Previous Next

PreviousPrevNext