What is amortized complexity?

AlgorithmsJunior~3 min read

Short answer

Amortized complexity is the average cost of one operation across a long sequence of operations on a data structure, where rare "expensive" steps are spread across many "cheap" ones. It does not rely on probability; it gives guarantees over sequences of operations. Classic examples: a push into a dynamic array and dequeue/enqueue in a queue built on two stacks run in amortized O(1), even though an individual operation can sometimes cost O(n).

Detailed answer

Why an amortized estimate is needed

Rare expensive operations (for example, growing an array) should not "spoil" the picture when their cost is covered by many cheap operations.
Unlike the average (probabilistic) case, amortized analysis assumes no distributions; it guarantees an upper bound for any sequence of operations.
It is used to explain why an interface stays fast "on average per operation" even though individual calls are sometimes expensive.

Methods of amortized analysis

The aggregate method: compute the total cost T(n) of a whole series of n operations and divide by n. The amortized cost = T(n)/n.
The accounting method: assign each operation a "credit" (a nominal cost). Cheap operations pay a bit more than their real price, building up a reserve that covers the rare expensive operations.
The potential method: introduce a potential function Φ(state) ≥ 0. The amortized cost of operation i: ĉ_i = c_i + Φ(S_i) − Φ(S_{i−1}). The sum of ĉ_i gives an upper bound on the total real cost.

Example 1: a dynamic array (push), amortized O(1)

A dynamic array doubles its capacity on overflow: a plain push costs O(1), but the rare grow operation is O(n), since n elements must be copied.

javascript

class DynArray {
  constructor() {
    this.capacity = 1;
    this.size = 0;
    this.data = new Array(this.capacity);
  }
  push(x) {
    if (this.size === this.capacity) {
      const newCapacity = this.capacity * 2;
      const newData = new Array(newCapacity);
      for (let i = 0; i < this.size; i++) newData[i] = this.data[i];
      this.data = newData;
      this.capacity = newCapacity;
    }
    this.data[this.size++] = x;
  }
}

Aggregate analysis: on a doubling we copy the current number of elements. Given n insertions, each element gets moved during a grow at most once per order of growth (1→2→4→8→...). The total number of copies is ≤ 2n, so T(n) ≤ c1·n + c2·2n = O(n), and the amortized cost of push equals O(1).

Potential analysis (the idea): you can take Φ = 2·size − capacity (clamped to zero from below). Then a plain push increases the potential, "storing up" credit; when a grow happens, the real cost of copying is paid for by a drop in the potential.

Example 2: a queue on two stacks, amortized O(1)

Two stacks (in, out): enqueue pushes onto in; dequeue pops from out, and if out is empty it first pours every element from in into out. Pouring is expensive, but each element is poured at most once, so the total is O(n) for n operations, that is, O(1) amortized.

javascript

class Queue {
  constructor() {
    this.in = [];
    this.out = [];
  }
  enqueue(x) { this.in.push(x); }
  dequeue() {
    if (this.out.length === 0) {
      while (this.in.length) this.out.push(this.in.pop());
    }
    if (this.out.length === 0) return undefined; // empty
    return this.out.pop();
  }
}

Comparing the estimates

Worst case: an upper bound for a single operation or input (for example, push with a grow is O(n)).
Average case: the mathematical expectation over a distribution of inputs/hashes.
Amortized case: an upper bound on the average cost over a sequence of operations, without probabilistic assumptions.

Where it shows up in practice

Dynamic arrays and strings (resizing by doubling).
A queue on two stacks, a deque on two lists.
Hash tables: insert/lookup operations are O(1) amortized when rehashing is rare and the load factor is controlled.
Union-Find (DSU) with path compression: almost constant, amortized (O(α(n))).

Pitfalls and caveats

An amortized estimate applies to long series of operations; an individual operation can still be expensive.
If an adversary deliberately picks the sequences, intuitive estimates can sometimes be "broken", check the model's assumptions.
In hard real-time systems an amortized constant may not be enough; a strict upper bound is needed for every operation.

Cheat sheet

The amortized cost of an operation = (the total cost of the sequence) / (the number of operations). The idea: rare expensive steps are paid for by many cheap ones.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.