Amortised Analysis

Some operations are usually instant and occasionally expensive. Amortised analysis is how you describe that honestly instead of quoting either extreme.

The problem it solves

A dynamic array has a fixed capacity. When you push past it, the engine allocates a bigger block and copies everything across - an O(n) operation. So how is push described as O(1)?

Because the expensive step is rare, and it gets rarer as the array grows. Capacity doubles each time, so the copies happen at sizes 1, 2, 4, 8, 16 and so on. Across n pushes the total copying work is about 2n, which averages to a constant per push.

// A dynamic array, written out so the copying is visible.
class Growable {
  constructor() {
    this.data = new Array(1)
    this.length = 0
    this.copies = 0
  }

  push(value) {
    if (this.length === this.data.length) {
      const bigger = new Array(this.data.length * 2)
      for (let i = 0; i < this.length; i++) bigger[i] = this.data[i]
      this.copies += this.length     // the expensive step
      this.data = bigger
    }
    this.data[this.length++] = value
  }
}

const list = new Growable()
for (let i = 0; i < 1000; i++) list.push(i)

console.log(list.copies)                    // 1023
console.log(list.copies / list.length)      // ~1.02 per push

A thousand pushes cost about a thousand element copies in total - roughly one each, not a thousand each. That is what amortised O(1) means.

Amortised is not average

This distinction gets asked about, and the answer is worth having ready.

• Average case is a statement about typical inputs. It assumes a distribution, and an unlucky input can break it - quicksort is O(n log n) on average and O(n²) on a bad pivot sequence.
• Amortised is a guarantee about a sequence of operations, with no assumption about the data. Any n pushes cost O(n) total. There is no unlucky input that makes it worse.

So amortised is the stronger claim. Hash map lookup is average-case O(1) - adversarial keys that all collide degrade it. Array push is amortised O(1) - nothing degrades it.

Where it matters in practice

When a single slow operation is unacceptable even if the average is fine. A game loop or an animation frame that occasionally takes 40ms to grow an array will drop a frame, and the user sees a stutter - the amortised average is no comfort. Preallocating with new Array(n) avoids the spikes entirely.

The same reasoning covers the pointer-based queue that compacts occasionally, and the path compression in Union-Find: rare cleanup work paid for by the many cheap operations around it.