Amortized Analysis

The asymptotic tools from the previous lessons bound a single operation in the worst case. But for many data structures that bound is misleading. Appending to a dynamic array is usually $O(1)$ (write into the next free slot), yet once in a while the array is full and the append must copy every element to a larger block, costing $\Theta (n)$. Bounding each append by its worst case, $O(n)$, and multiplying by $n$ appends gives $O(n^2)$, which hugely overstates the truth: $n$ appends really take $\Theta (n)$ total. The expensive copies are rare, and the cheap appends between them more than pay for them.

Amortized analysis is the technique for making that intuition rigorous. It charges each operation an amortized cost so that the total over any sequence is correct, while individual amortized costs are smooth and easy to reason about.

What amortized means — and does not

Fix a data structure and consider a sequence of $m$ operations performed on it.

The point of the definition is that the amortized costs need only upper-bound the actual total; we are free to choose smooth ${\hat{c}}_i$ that overcharge cheap operations and undercharge expensive ones, as long as the running sum never falls behind. If every ${\hat{c}}_i\le \hat{c}$, then $m$ operations cost at most $m\hat{c}$ in total, no matter how the costs are distributed inside the sequence.

The distinction matters in both directions. An average-case bound can be excellent on random inputs and useless against the one input your program actually sees; an amortized bound cannot. Conversely, an amortized bound says nothing about any single operation, only about prefixes of the sequence: the $i$-th append may well cost $\Theta (i)$, and the guarantee only promises that the operations before it were cheap enough to compensate. We return to when that trade is unacceptable at the end.

The three classical methods (aggregate, accounting, and potential) all certify the same kind of bound; they differ only in bookkeeping.¹ Each is developed below, first on one running example so the methods can be compared side by side, then on a second structure so the mechanics show twice.

The running example: dynamic-array doubling

A table holds $num$ items in a block of $size$ slots. $\text{Table-Insert}$ writes into the next free slot; but when the block is full ($num=size$), it first doubles the block, allocating $2\cdot size$ slots and copying all $num$ existing items over, then inserts.

Count the cost of an insert as $1$ for the write plus, when it doubles, the number of items copied. Inserts that do not trigger a doubling cost $1$. The $i$-th insert triggers a doubling exactly when $i-1$ is a power of $2$, copying $i-1$ items, so its cost is $i$. Plotting cost against operation index shows the characteristic picture: a flat baseline of $1$, punctuated by spikes at $i=2,3,5,9,17,\dots$ that double in height.

The naive analysis multiplies the worst single insert, $\Theta (n)$, by $n$ inserts and concludes $O(n^2)$. The truth is $\Theta (n)$ total, amortized $O(1)$ per insert, and each of the three methods proves it in its own vocabulary. Watch how the same fact, that cheap inserts outnumber and prepay the copies, gets encoded three different ways.

Method 1: aggregate analysis

The aggregate method is the most direct: bound the total cost of any sequence of $m$ operations as a whole, then divide by $m$. Every operation is assigned the same amortized cost, $\hat{c}=T(m)/m$, where $T(m)$ is the worst-case total.

The dynamic array: sum the sequence

For $n$ inserts into an initially empty table, separate the two kinds of work. Every insert performs exactly one write, contributing $n$ in total. The copies happen only at doublings: the insert at index $i=2^j+1$ copies $2^j$ items, and doublings occur for every $j$ with $2^j\le n-1$. The total number of items copied is therefore a geometric sum:

Adding the writes,

so the amortized cost per insert is $T(n)/n<3$. Concretely, for $n=16$: the writes cost $16$, the doublings copy $1+2+4+8=15$ items, and the total is $31<48=3\cdot 16$. The spikes in the figure above are tall, but their combined area is smaller than the baseline they interrupt.

The whole argument is one sum. That is the aggregate method's appeal: when the total can be computed directly, nothing more is needed.

A stack with multipop

The second aggregate example needs a global counting argument rather than a closed-form sum. Augment the usual stack ($\text{Push}$ and $\text{Pop}$, each $O(1)$) with one more operation, $\text{Multipop}(k)$, which pops the top $\min (k,s)$ items, where $s$ is the current size.

A single $\text{Multipop}$ can be expensive: on a stack of $s$ items, $\text{Multipop}(s)$ runs the loop $s$ times, costing $\Theta (s)$. With $s$ as large as $m$, the naive per-operation bound is $O(m)$, suggesting $O(m^2)$ for the whole sequence.

That bound is far too pessimistic. One fact tightens it: each item is popped at most once for each time it is pushed. Over a sequence of $m$ operations there are at most $m$ pushes, so the total number of pop actions, whether by $\text{Pop}$ or inside $\text{Multipop}$, is at most $m$. Every operation does $O(1)$ work besides popping, contributing another $O(m)$. Hence the total cost of any sequence of $m$ operations is $O(m)$.

Aggregate analysis is appealing when a clean global count (here, pops $\le$ pushes) bounds the total directly. Its limitation is that it assigns one cost to all operation types; the next two methods let us charge them differently.

from __future__ import annotations

from typing import Generic, Optional, TypeVar

Item = TypeVar("Item")

class StackNode(Generic[Item]):
  """
    One stack cell: its value and a link down to the cell beneath it.\n
    The bottom cell links to None.\n
  """

  def __init__(self, value: Item, below: Optional[StackNode[Item]]) -> None:
    self.value: Item = value
    self.below: Optional[StackNode[Item]] = below

  def __repr__(self) -> str:
    return f"StackNode({self.value!r})"

class MultipopStack(Generic[Item]):
  """
    A LIFO stack of linked nodes supporting push, pop, and multipop.\n
    Tracks `cost` — the running count of elementary pop actions — so the\n
    amortized argument (total pops <= total pushes) can be checked\n
    directly against an executed sequence.\n
  """

  def __init__(self) -> None:
    self._top: Optional[StackNode[Item]] = None
    self._size: int = 0
    self.cost: int = 0

  def __len__(self) -> int:
    return self._size

  def is_empty(self) -> bool:
    """
      Whether the stack holds no items.\n
    """
    return self._size == 0

  def push(self, value: Item) -> None:
    """
      Place `value` on top of the stack. Costs one unit of work.\n
    """
    # link a fresh node above the current top.
    self._top = StackNode(value, self._top)
    self._size += 1
    self.cost += 1

  def pop(self) -> Item:
    """
      Remove and return the top item. Raises IndexError when empty.\n
    """
    top = self._top
    if top is None:
      raise IndexError("pop from an empty stack")
    self._top = top.below
    self._size -= 1
    self.cost += 1
    return top.value

  def peek(self) -> Item:
    """
      Return the top item without removing it. Raises when empty.\n
    """
    if self._top is None:
      raise IndexError("peek into an empty stack")
    return self._top.value

  def multipop(self, count: int) -> list[Item]:
    """
      Pop and return the top min(count, size) items, top-most first.\n
      A non-positive `count` pops nothing.\n
    """
    popped: list[Item] = []
    while self._top is not None and count > 0:
      popped.append(self.pop())
      count -= 1
    return popped

Method 2: the accounting method

The accounting method assigns each operation type its own amortized cost, called its charge, which may differ from its actual cost. When an operation's charge exceeds its actual cost, the surplus is stored as credit on specific elements of the data structure; when an operation costs more than its charge, it spends stored credit to cover the difference. Erickson develops the same idea as taxation: overtax the cheap operations and let the treasury pay for the expensive ones.²

The one rule that makes this a valid proof:

If credit stays non-negative, the amortized charges upper-bound the actual costs over every prefix, matching the definition, so the per-operation charges are a valid amortized bound.

The dynamic array: charge three dollars per insert

The aggregate bound of $3$ per insert suggests the scheme: charge every $\text{Table-Insert}$ exactly $3$ units. Spend them as follows.

1. $1$ unit pays for writing the new item into its slot.
2. $1$ unit is banked on the new item itself, reserved for the next time a doubling copies it.
3. $1$ unit is banked on the new item on behalf of one older item — one that was already copied by the last doubling and has no credit left.

Why the third unit works out: right after a doubling to capacity $size$, the table holds exactly $size/2$ items, all with zero credit (the doubling spent it). Before the next doubling can fire, another $size/2$ inserts must arrive. Each new item banks $2$ units, one for its own future copy and one for exactly one credit-less older item; the $size/2$ new items cover the $size/2$ older items one-for-one.

When the table fills at $num=size$, the $size/2$ newcomers hold $2\cdot size/2=size$ units — exactly the cost of copying all $size$ items into the new block. The doubling spends every credit, the copied items land in the new block with no credit, and the invariant is re-established with the table again half full. No operation ever overdraws, so the charge of $3$ is a valid amortized cost.

The scheme also explains the constant. Two units would not suffice: a new item could pay for its own future copy but not for the older item copied in the same doubling. Charging $3$ keeps the credit non-negative.

The binary counter

The second accounting example. A $k$-bit binary counter starts at $0$ and supports $\text{Increment}$, which adds $1$. The cost of an increment is the number of bits it flips.

A single increment can flip many bits: incrementing $0111$ to $1000$ flips four. In the worst case ($\underset{k}{\underbrace{1\cdots 1}}\to \underset{k}{\underbrace{0\cdots 0}}$, then a carry out) an increment costs $\Theta (k)$, so $n$ increments appear to cost $O(nk)$.

The truth is $O(n)$, and the accounting method shows it cleanly. Charge each increment $2$ units, and store $1$ unit of credit on every bit that is set to $1$. When a bit flips $0\to 1$, pay $1$ unit for the flip and bank $1$ unit on that bit. When a bit flips $1\to 0$ inside the carry loop, pay for the flip with the credit already sitting on that bit — for free, from the increment's perspective.

Each $\text{Increment}$ sets exactly one bit to $1$ (the bit $A[i]$ at the end), so it banks exactly one new credit and spends $2$ units total: $1$ to flip that bit up, $1$ to bank. Every $1\to 0$ flip in the carry chain is already paid for. Credit equals the number of $1$-bits in the counter, which is never negative, so the invariant holds.

The aggregate method reaches the same constant from a different direction, and the cross-check is worth seeing. Bit $0$ flips on every increment; bit $1$ on every second; in general bit $i$ flips only when the increment count crosses a multiple of $2^i$, so over $n$ increments it flips $\lfloor n/2^i\rfloor$ times. The total number of flips is

amortized cost less than $2$ per increment — the same $2$ the accounting scheme charges. Half of all the work happens in bit $0$, a quarter in bit $1$, and the tail vanishes geometrically.

The accounting method's strength is its locality: credit lives on concrete elements (here, the $1$-bits), and you verify the bound by checking that whoever pays an expensive operation's cost has the credit on hand.

class BinaryCounter:
  """
    A fixed-width binary counter over `width` bits, low bit first.\n
    `bits[0]` is the least significant bit. Increment flips a run of\n
    trailing 1s down to 0 (the carry) then sets the first 0 bit;\n
    overflow past the top bit wraps to zero. `cost` accumulates the total\n
    number of bit flips performed, the actual cost being analysed.\n
  """

  def __init__(self, width: int) -> None:
    if width < 0:
      raise ValueError("width must be non-negative")
    self.width: int = width
    self.bits: list[int] = [0 for _ in range(width)]
    self.cost: int = 0

  def increment(self) -> int:
    """
      Add one to the counter and return the number of bits flipped\n
      by this single operation (its actual cost).\n
    """
    flips: int = 0
    index: int = 0

    # flip the run of trailing 1s down to 0 — propagate the carry leftward.
    while index < self.width and self.bits[index] == 1:
      self.bits[index] = 0
      flips += 1
      index += 1

    # set the first 0 bit; skipped on a full-width overflow (wraps to 0).
    if index < self.width:
      self.bits[index] = 1
      flips += 1

    self.cost += flips
    return flips

  def value(self) -> int:
    """
      The non-negative integer the bits currently encode.\n
    """
    # sum the place values of the set bits.
    return sum(1 << index for index, bit in enumerate(self.bits) if bit)

  def popcount(self) -> int:
    """
      The number of 1-bits — equal to the credit banked by accounting.\n
    """
    return sum(self.bits)

  def __str__(self) -> str:

    # most significant bit first, matching how integers are written.
    return "".join(str(bit) for bit in reversed(self.bits))

Method 3: the potential method

The potential method is the most flexible and the one used most in practice. Instead of tracking credit on individual elements, it assigns the entire data structure a single number, the potential $\Phi$, that measures stored-up work. An operation's amortized cost is its actual cost plus the change in potential it causes.

Why this works: the potential changes telescope. Summing over the sequence,

Since $\Phi (D_m)\ge \Phi (D_0)$, the trailing term is non-negative, so $\sum c_i\le \sum {\hat{c}}_i$ — precisely the amortized-cost definition. An expensive operation (large $c_i$) is affordable only if it drops the potential enough to offset itself; a cheap operation that builds potential pre-pays for the expensive one to come.

The dynamic array, one more time

Aggregate summed the sequence and accounting placed coins on items; the potential method compresses both into one function, and the same idea will reappear for deletion and for resizing hash tables. Choose the potential to measure how close the table is to overflowing:

Right after a doubling the table is half full ($num=size/2$ before the pending insert lands), so $\Phi$ is small; just before the next doubling it is completely full ($num=size$), so $\Phi =num$ — exactly enough banked potential to pay for copying all $num$ items. The potential is never negative because the table is always at least half full once it has grown. Plotted over a run of inserts, $\Phi$ sawtooths: up by $2$ per cheap insert, falling back down whenever a doubling spends it.

The doubling expense is invisible in the amortized cost: a doubling insert costs the same flat $3$ as a trivial one, because the potential it consumes ($\Phi$ drops from ${num}_{i-1}$ back to $2$) matches the potential the cheap inserts before it built up. That is the whole mechanism, and it is why the flat dashed line in the cost figure sits at $3$ no matter how tall the spikes.

The binary counter, one more time

The counter's accounting scheme kept a coin on every $1$-bit; the corresponding potential is simply the coin count:

Suppose the $i$-th increment resets $t_i$ trailing $1$s to $0$ and then sets one bit to $1$. Its actual cost is $c_i=t_i+1$, and the number of $1$-bits changes by ${\Phi }_i-{\Phi }_{i-1}=1-t_i$. The amortized cost is

for every increment, no matter how long the carry chain: a long chain has a large $c_i$ and an equally large potential drop, and the two cancel except for the constant. (If the counter overflows — all $k$ bits are $1$ and the increment clears them all — then $c_i=k$, the potential drops by $k$, and the amortized cost is $0\le 2$.) Since ${\Phi }_0=0$ and $\Phi \ge 0$, the telescoped total is $\sum c_i\le 2n$: the same bound as before, now with no coins to track.

from typing import Generic, Optional, TypeVar

Item = TypeVar("Item")

class DynamicArray(Generic[Item]):
  """
    A growable, array-backed list that doubles its block when full.\n
    Backed by a flat list of fixed `capacity` whose first `count` slots\n
    hold the live items — the canonical array representation, not nested.\n
    `cost` totals the elementary work (writes plus copies) so the\n
    O(n)-for-n-appends bound can be checked against an executed run.\n
  """

  def __init__(self, growth_factor: int = 2) -> None:
    if growth_factor < 2:
      raise ValueError("growth_factor must be at least 2")
    self.growth_factor: int = growth_factor
    self._slots: list[Optional[Item]] = []
    self._count: int = 0
    self.cost: int = 0

  def __len__(self) -> int:
    return self._count

  @property
  def capacity(self) -> int:
    """
      The number of slots in the current backing block.\n
    """
    return len(self._slots)

  def potential(self) -> int:
    """
      The potential Phi = 2*count - capacity used in the amortized proof.\n
      Non-negative once the array has grown (it stays at least half full).\n
    """
    return 2 * self._count - self.capacity

  def _resize(self, new_capacity: int) -> None:
    """
      Move the live items into a fresh block of `new_capacity` slots,\n
      charging one unit per item copied — the expensive step.\n
    """
    # copy each live item into the new block, charging one unit per move.
    new_slots: list[Optional[Item]] = [None for _ in range(new_capacity)]
    for index in range(self._count):
      new_slots[index] = self._slots[index]
      self.cost += 1

    self._slots = new_slots

  def append(self, value: Item) -> None:
    """
      Add `value` to the end, growing the block first if it is full.\n
    """
    # grow the block (geometrically) when it is full, before the write.
    if self._count == self.capacity:
      grown: int = self.capacity * self.growth_factor
      new_capacity: int = 1 if self.capacity == 0 else grown
      self._resize(new_capacity)

    # write into the next free slot in O(1).
    self._slots[self._count] = value
    self._count += 1
    self.cost += 1

  def get(self, index: int) -> Item:
    """
      The item at `index`, supporting Python-style negative indices.\n
    """
    # normalise a negative index, then bounds-check against live items.
    position: int = index + self._count if index < 0 else index
    if not 0 <= position < self._count:
      raise IndexError("index out of range")

    value = self._slots[position]
    assert value is not None
    return value

  def __getitem__(self, index: int) -> Item:
    return self.get(index)

  def to_list(self) -> list[Item]:
    """
      A plain list of the live items in insertion order.\n
    """
    # walk the live prefix, asserting each slot was filled.
    result: list[Item] = []
    for index in range(self._count):
      value = self._slots[index]
      assert value is not None
      result.append(value)

    return result

class LinearGrowthArray(Generic[Item]):
  """
    A dynamic array that grows by a fixed `increment` of slots rather than\n
    multiplying — the counter-example showing why geometric growth matters.\n
    Reallocating every `increment` appends copies c, 2c, 3c, ... items,\n
    which sum to Theta(n^2 / increment): amortized Theta(n) per append, not\n
    O(1). Same interface as `DynamicArray`, with `cost` for comparison.\n
  """

  def __init__(self, increment: int = 1) -> None:
    if increment < 1:
      raise ValueError("increment must be at least 1")
    self.increment: int = increment
    self._slots: list[Optional[Item]] = []
    self._count: int = 0
    self.cost: int = 0

  def __len__(self) -> int:
    return self._count

  @property
  def capacity(self) -> int:
    """
      The number of slots in the current backing block.\n
    """
    return len(self._slots)

  def append(self, value: Item) -> None:
    """
      Add `value`, growing by a fixed increment when the block is full.\n
    """
    # when full, grow by a fixed increment and copy every item across.
    if self._count == self.capacity:
      grown: int = self.capacity + self.increment
      new_slots: list[Optional[Item]] = [None for _ in range(grown)]
      for index in range(self._count):
        new_slots[index] = self._slots[index]
        self.cost += 1
      self._slots = new_slots

    # write into the next free slot.
    self._slots[self._count] = value
    self._count += 1
    self.cost += 1

  def to_list(self) -> list[Item]:
    """
      A plain list of the live items in insertion order.\n
    """
    # walk the live prefix, asserting each slot was filled.
    result: list[Item] = []
    for index in range(self._count):
      value = self._slots[index]
      assert value is not None
      result.append(value)

    return result

Choosing a method

All three methods prove the same bound; the choice is one of convenience.

Aggregate and accounting can be seen as special cases of the potential method, with the potential playing the role of remaining budget and total stored credit respectively, so when in doubt, reach for a potential function. The array and counter examples above show the translation: the counter's $\Phi$ (count of $1$-bits) is its total accounting credit, and the array's $\Phi =2num-size$ equals the credits held by items inserted since the last doubling.

When an amortized bound is not enough

An amortized $O(1)$ insert still permits a single insert that costs $\Theta (n)$. For throughput (total work over the whole sequence) that is irrelevant. For latency it can be fatal: an audio callback, a game frame, a real-time control loop, or a packet-processing path that stalls for one $\Theta (n)$ copy misses its deadline, and the average is irrelevant to that one pause. Amortized analysis answers how much work in total, not how long is the longest pause.

When the pause matters, the standard remedy is to de-amortize: keep both the old and the new block during growth and move a constant number of items on every subsequent insert, so the copy finishes before the new block itself fills. Every operation then costs $O(1)$ in the worst case, at the price of extra space and constant-factor overhead. Real-time and latency-sensitive systems pay that price; everything else takes the simpler amortized structure.

Where amortized analysis recurs

This machinery recurs throughout the course. It is the only accurate way to state the running time of several data structures you will meet later:

• Union–Find. With union by rank and path compression, a sequence of $m$ operations runs in $O(m\alpha (n))$ amortized time, where $\alpha$ is the inverse Ackermann function — effectively constant. The proof is a sophisticated potential argument.
• Hash tables. A hash table that doubles (and halves) its bucket array to keep the load factor bounded uses exactly the $\text{Table-Insert}$ argument above, giving amortized $O(1)$ insert and delete.
• Dynamic arrays (vector, ArrayList, Python list) are the doubling table itself; their $O(1)$ amortized append is what makes them the default sequence container.³

The recurring moral: when worst-case-per-operation overcounts because expensive steps are rare and self-limiting, amortize.

Persistence and competitive analysis

Two threads extend the machinery here. The first is persistent and functional data structures. The accounting and potential methods assume the structure is used linearly — each version replaces the last — so banked credit is spent at most once. When an old version can be reused (as in a purely functional setting, where nothing is mutated in place), a naive amortized bound breaks, because an adversary can repeatedly force the one expensive operation the credit was saved for. Okasaki's work resolves this with lazy evaluation and scheduling: memoized thunks make the expensive step happen only once even under reuse, restoring the amortized bound and yielding functional queues and deques with the same $O(1)$ amortized costs as their imperative cousins.⁴ His names for the accounting and potential methods — the banker's and physicist's methods — are now standard.

The second thread is competitive analysis, which applies the same average-over-a-sequence idea to online algorithms that must respond to each request before seeing the next. The self-adjusting splay tree of Sleator and Tarjan achieves $O(\log n)$ amortized cost per operation through a potential argument almost identical to the ones above, and their move-to-front and paging results launched the study of how well an online algorithm can do against an adversary that knows the future.⁵ Amortized analysis, in short, is the entry point to a much larger theory of sequences of operations rather than single ones.

Takeaways

• Amortized cost is the worst-case average over a sequence: assign ${\hat{c}}_i$ with $\sum c_i\le \sum {\hat{c}}_i$ for every sequence. It is not expected or average-case — there is no probability anywhere, and the bound survives an adversarial input.
• Aggregate: bound the whole sequence's cost, divide by $m$. For the array, $n$ writes plus copies $1+2+4+\cdots <2n$ give a total under $3n$; multipop is $O(1)$ amortized because total pops $\le$ total pushes; the counter flips ${\sum }_i\lfloor n/2^i\rfloor <2n$ bits.
• Accounting: overcharge cheap operations, bank the surplus as credit on elements, spend it on expensive ones; keep credit $\ge 0$. Charge $3$ per append (write, own future copy, one older item's copy) or $2$ per increment (flip a bit up, bank a coin on it).
• Potential: encode banked work as $\Phi (D)$; then ${\hat{c}}_i=c_i+\Phi (D_i)-\Phi (D_{i-1})$, and the changes telescope. Doubling arrays: $\Phi =2num-size$, amortized $3$. The counter: $\Phi =$ number of $1$-bits, amortized $2$.
• Geometric growth is essential: doubling makes the copy cost telescope to a constant; growing by a fixed increment gives $\Theta (n)$ amortized.
• An amortized bound is a throughput guarantee, not a latency guarantee: individual operations may still stall for $\Theta (n)$. Real-time systems de-amortize (incremental copying) to get worst-case $O(1)$ at a constant-factor price.
• The technique underpins union–find, resizable hash tables, and every dynamic array.