Amortized Analysis

Worst-case Big-O can be misleading when an expensive operation is rare. Amortized analysis averages the cost across a full sequence of operations to give a more honest picture of real-world performance.

The Dynamic Array Problem

A dynamic array (like JavaScript’s Array) allocates a fixed internal buffer. When you push beyond that buffer, it must:

1. Allocate a new, larger buffer (typically 2× the old size)
2. Copy every existing element into the new buffer
3. Append the new element

That resize is O(n). Does that mean push is O(n)? Not in practice.

Aggregate Method

Count the total work for n pushes and divide by n.

Suppose you start with a buffer of size 1 and double on each overflow:

• Push 1: insert. Cost 1.
• Push 2: resize (copy 1) + insert. Cost 2.
• Push 3: resize (copy 2) + insert. Cost 3.
• Push 4: insert (buffer has space). Cost 1.
• Push 5: resize (copy 4) + insert. Cost 5.

After n pushes, total resize cost is 1 + 2 + 4 + 8 + … ≤ 2n. Insert cost is n. Grand total ≤ 3n. Divide by n → O(1) amortized per push.

// Simulate a doubling dynamic array
function makeDynamicArray() {
  let buf = new Array(1);
  let size = 0;
  let capacity = 1;

  return {
    push(val) {
      if (size === capacity) {
        // Resize — O(n) but rare
        capacity *= 2;
        const next = new Array(capacity);
        for (let i = 0; i < size; i++) next[i] = buf[i];
        buf = next;
      }
      buf[size++] = val;
    },
    get length() { return size; },
  };
}

const arr = makeDynamicArray();
for (let i = 0; i < 100; i++) arr.push(i);
console.log(arr.length); // 100

Banker’s Method

The banker’s method assigns each operation a “credit” — a notional coin you save on cheap operations to pay for future expensive ones.

Assign each push 3 coins:

• 1 coin pays for the insert itself.
• 2 coins go into a savings account tied to the element.

When a resize occurs for a buffer of size n, there are at least n/2 elements that have saved 2 coins each — enough to pay for copying all n elements. The amortized cost is 3 coins, which is O(1).

Why It Matters for JavaScript

V8’s Array implementation uses a doubling strategy internally. When you write:

const results = [];
for (const item of bigDataset) {
  results.push(transform(item)); // amortized O(1)
}

You are paying O(1) amortized per push. Over 1 million pushes, total resize work is bounded by 2 million copies — not 1 million × 1 million.

The alternative — pre-allocating with new Array(n) — avoids all resizes entirely, which can matter when n is known ahead of time and the constant factor matters:

const n = bigDataset.length;
const results = new Array(n); // single allocation
for (let i = 0; i < n; i++) {
  results[i] = transform(bigDataset[i]);
}

V8 treats new Array(n) as a hint to allocate the full buffer upfront, making every write O(1) with no resizes.

Up Next

Time complexity tells half the story. The other half is how much memory your algorithm uses as input grows.