jsschools

Amortized Analysis

A technique that averages the cost of operations over a sequence to show that expensive operations occur rarely enough that the per-operation average is cheap.

Spec ↗

Syntax

// Amortized cost = total cost of n operations / n
// Three methods: aggregate, accounting (banker's), potential (physicist's)

Parameters

NameTypeRequiredDescription
operations Array<() => void> Yes A sequence of n operations whose total cost is analysed together.
n number No Length of the operation sequence. The amortized cost is total/n.

Returns

number — The amortized cost per operation (total cost / n).

Examples

// Dynamic array (like JavaScript's Array) push — amortized O(1)
// Doubling strategy: capacity doubles when full.
// After n pushes total copy work = 1 + 2 + 4 + ... + n ≤ 2n = O(n)
// So amortized cost per push = O(n)/n = O(1).

class DynamicArray {
  #data = new Array(1); #cap = 1; #size = 0;
  push(val) {
    if (this.#size === this.#cap) {
      const next = new Array(this.#cap * 2);
      for (let i = 0; i < this.#size; i++) next[i] = this.#data[i];
      this.#data = next; this.#cap *= 2;
      // ↑ This O(n) resize is rare — 1 resize per n/2 pushes.
    }
    this.#data[this.#size++] = val;
  }
  get(i) { return this.#data[i]; }
  get size() { return this.#size; }
}

const da = new DynamicArray();
for (let i = 0; i < 10; i++) da.push(i * 10);
console.log(da.size, da.get(9));
Output 
10 90

// Counting sort-style demonstration:
// Total cost of incrementing a k-bit binary counter n times
// is O(n) — amortized O(1) per increment.
// Bit i flips once every 2^i increments, so total flips = Σ n/2^i < 2n.

function binaryCounter(bits, increments) {
  const counter = new Array(bits).fill(0);
  let totalFlips = 0;
  for (let op = 0; op < increments; op++) {
    let i = 0;
    while (i < bits && counter[i] === 1) { counter[i] = 0; i++; totalFlips++; }
    if (i < bits) { counter[i] = 1; totalFlips++; }
  }
  return { value: parseInt([...counter].reverse().join(''), 2), totalFlips };
}
const result = binaryCounter(8, 16);
console.log(`counter=${result.value}, flips=${result.totalFlips}, avg=${result.totalFlips/16}`);
Output 
counter=16, flips=31, avg=1.9375

Notes

Three methods of amortized analysis: 1. **Aggregate**: total cost T(n) for n ops → amortized = T(n)/n. 2. **Accounting**: assign a "credit" to cheap ops to pre-pay for expensive ops. Show credits always ≥ 0. 3. **Potential**: define Φ (potential function) on data structure state. Amortized cost = actual cost + ΔΦ. If Φ never goes negative the amortized cost is an upper bound on average actual cost. Classic examples: - Dynamic array push: amortized O(1) via doubling. - Splay tree operations: amortized O(log n). - Union-Find with path compression: amortized O(α(n)). - Stack with multi-pop: amortized O(1) per push or pop.

See also