---
title: Amortized Analysis
module: Foundations
moduleNumber: 1
lessonNumber: 6
order: 106
summary: |
  Some operations are occasionally expensive but cheap on average across any
  sequence. Amortized analysis bounds the average cost per operation over a
  worst-case sequence — not an expectation — so a rare costly step is paid for by
  the many cheap ones around it. This lesson develops the aggregate, accounting,
  and potential methods on dynamic-array doubling, the binary counter, and a
  stack with multipop.
topics: [Amortized Analysis]
sources:
  - book: CLRS
    ref: "Ch. 16 — Amortized Analysis"
  - book: Skiena
    ref: "§3.4 — Dynamic Arrays; §8.2 — Aggregate Analysis"
  - book: Erickson
    ref: "Ch. 1 — Amortized analysis of data structures"
practice:
  - title: 'Min Stack'
    slug: min-stack
    difficulty: Medium
  - title: 'Design Circular Queue'
    slug: design-circular-queue
    difficulty: Medium
  - title: 'Number of 1 Bits'
    slug: number-of-1-bits
    difficulty: Easy
  - title: 'Implement Stack using Queues'
    slug: implement-stack-using-queues
    difficulty: Easy
---

The asymptotic tools from [the previous lessons](/algorithms/foundations/asymptotic-analysis)
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.

> **Definition (amortized cost).** Assign each operation an _amortized cost_
> $\hat{c}_i$ such that for **every** sequence of $m$ operations,
> $$
> \sum_{i=1}^{m} c_i \;\le\; \sum_{i=1}^{m} \hat{c}_i,
> $$
> where $c_i$ is the actual cost of the $i$-th operation. The amortized cost
> _per operation_ is then $\frac{1}{m}\sum_i \hat{c}_i$.

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.

> **Remark (not the average case).** Amortized analysis is a _worst-case_
> guarantee, not a probabilistic one. It makes **no assumption** about the
> distribution of inputs and involves **no randomness or expectation**. The
> bound holds for the single worst sequence an adversary can construct. This
> separates it from average-case analysis, which averages over a _distribution
> of inputs_ and can be defeated by a bad input. An amortized $O(1)$ bound says:
> pick any sequence you like, and the per-operation average is still $O(1)$.

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](#when-an-amortized-bound-is-not-enough).

The three classical methods (**aggregate**, **accounting**, and **potential**)
all certify the same kind of bound; they differ only in bookkeeping.[^clrs-amort]
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 $\mathit{num}$ items in a block of $\mathit{size}$ slots.
$\textsc{Table-Insert}$ writes into the next free slot; but when the block is
full ($\mathit{num} = \mathit{size}$), it first **doubles** the block, allocating
$2\cdot\mathit{size}$ slots and copying all $\mathit{num}$ existing items over,
then inserts.

```algorithm
caption: $\textsc{Table-Insert}(T, x)$ — append $x$, doubling when full
number: 1
if $T.\mathit{size} = 0$ then
  allocate $T.\mathit{table}$ with $1$ slot; $T.\mathit{size} \gets 1$
if $T.\mathit{num} = T.\mathit{size}$ then // block full: grow
  allocate $\mathit{new}$ with $2 \cdot T.\mathit{size}$ slots
  copy all $T.\mathit{num}$ items into $\mathit{new}$ // the expensive step
  $T.\mathit{table} \gets \mathit{new}$; $T.\mathit{size} \gets 2 \cdot T.\mathit{size}$
insert $x$ into $T.\mathit{table}[T.\mathit{num}]$; $T.\mathit{num} \gets T.\mathit{num} + 1$
return
```

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.

$$
% caption: Cost per $\textsc{Table-Insert}$ against operation index $i$. Most inserts
%          cost $1$ (the pale baseline); the $i$-th insert doubles exactly when $i - 1$
%          is a power of two, copying $i - 1$ items for a total cost of $i$. The spikes
%          double in height but also double in spacing, so their area spreads out to a
%          constant per insert: the dashed amortized line sits flat at $3$.
\begin{tikzpicture}[
  >={Stealth[length=2.4mm]},
  lbl/.style={font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-0.8,-0.7) rectangle (11.2,4.8);
  % axes
  \draw[->] (0,0) -- (9.6,0) node[lbl, right] {operation $i$};
  \draw[->] (0,0) -- (0,4.2);
  \node[lbl, anchor=south] at (0,4.25) {cost};
  % y ticks, linear scale: 0.4 per unit of cost
  \foreach \y/\v in {0.4/1, 1.2/3, 2.0/5, 3.6/9} {
    \draw (-0.08,\y) -- (0.08,\y);
    \node[lbl, anchor=east] at (-0.14,\y) {\v};
  }
  % x tick labels at the doubling indices
  \foreach \x/\v in {1.0/2, 1.5/3, 2.5/5, 4.5/9} {
    \node[lbl, anchor=north] at (\x,-0.10) {\v};
  }
  % unit-cost baseline bars for non-doubling inserts
  \foreach \x in {1,4,6,7,8,10,11,12,13,14,15,16} {
    \draw[acc!40, line width=1.4pt] ({\x*0.5},0) -- ({\x*0.5},0.4);
  }
  % doubling spikes: cost i at index i, same linear scale as the ticks
  \draw[acc, line width=1.8pt] (1.0,0) -- (1.0,0.8);   % i=2, cost 2
  \draw[acc, line width=1.8pt] (1.5,0) -- (1.5,1.2);   % i=3, cost 3
  \draw[acc, line width=1.8pt] (2.5,0) -- (2.5,2.0);   % i=5, cost 5
  \draw[acc, line width=1.8pt] (4.5,0) -- (4.5,3.6);   % i=9, cost 9
  \node[lbl, acc, anchor=south] at (1.0,0.86) {$2$};
  \node[lbl, acc, anchor=south] at (1.5,1.26) {$3$};
  \node[lbl, acc, anchor=south] at (2.5,2.06) {$5$};
  \node[lbl, acc, anchor=south] at (4.5,3.66) {$9$};
  % amortized line at cost 3
  \draw[densely dashed, black!70, line width=1pt] (0,1.2) -- (9.4,1.2);
  \node[lbl, anchor=south east] at (9.3,1.28) {amortized cost $3$};
\end{tikzpicture}
$$

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:

$$
\sum_{j=0}^{\lfloor \lg (n-1) \rfloor} 2^{\,j}
\;=\; 2^{\lfloor \lg (n-1) \rfloor + 1} - 1
\;\le\; 2(n-1) - 1
\;<\; 2n.
$$

Adding the writes,

$$
T(n) \;<\; n + 2n \;=\; 3n,
$$

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.

> **Theorem.** Any sequence of $n$ $\textsc{Table-Insert}$ operations on an
> initially empty table costs less than $3n$, so the amortized cost per insert
> is less than $3$.

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 ($\textsc{Push}$ and $\textsc{Pop}$,
each $O(1)$) with one more operation, $\textsc{Multipop}(k)$, which pops the top
$\min(k, s)$ items, where $s$ is the current size.

```algorithm
caption: $\textsc{Multipop}(S, k)$ — pop up to $k$ items off stack $S$
number: 2
while not $\textsc{Empty}(S)$ and $k > 0$ do
  call $\textsc{Pop}(S)$ // discard one item
  $k \gets k - 1$
return
```

A single $\textsc{Multipop}$ can be expensive: on a stack of $s$ items,
$\textsc{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
$\textsc{Pop}$ or inside $\textsc{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)$.

> **Theorem.** Starting from an empty stack, any sequence of $m$
> $\textsc{Push}$, $\textsc{Pop}$, and $\textsc{Multipop}$ operations runs in
> $O(m)$ time. The amortized cost per operation is $O(m)/m = O(1)$.

> **Proof.** Charge $\Theta(1)$ for the per-operation overhead, summing to
> $\Theta(m)$. The remaining work is pop actions. An item must be pushed before
> it is popped and is removed from the stack when popped, so the number of pops
> never exceeds the number of pushes, which is at most $m$. Total pop work is
> therefore $O(m)$, and the whole sequence costs $O(m)$. Dividing by $m$ gives
> amortized $O(1)$. $\qed$

$$
% caption: Why the total is $O(m)$: each item is pushed once and popped at most once, so
%          the dollar a push deposits pays for that item's eventual pop — whether by
%          $\textsc{Pop}$ or inside a $\textsc{Multipop}$. Total pops never exceed total
%          pushes, so the whole sequence does at most $m$ pop actions.
\begin{tikzpicture}[
  font=\footnotesize, >={Stealth[length=2.2mm]},
  item/.style={draw, minimum width=11mm, minimum height=6mm, fill=acc!18},
  lbl/.style={font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-2.0,-1.7) rectangle (8.6,2.4);
  % a stack: pushes deposit, multipop removes a run from the top
  \node[lbl, anchor=south] at (1.6,1.9) {push deposits};
  \node[item] (s1) at (1.6,1.2) {item};
  \node[item] (s2) at (1.6,0.5) {item};
  \node[item] (s3) at (1.6,-0.2) {item};
  \node[item] (s4) at (1.6,-0.9) {item};
  \node[lbl, anchor=east] at (0.9,-0.9) {bottom};
  \node[lbl, anchor=east] at (0.9,1.2) {top};
  % arrows for the popped run
  \draw[->, acc, line width=1pt] (2.5,1.2) -- (4.6,1.2);
  \draw[->, acc, line width=1pt] (2.5,0.5) -- (4.6,0.5);
  \node[lbl, acc, anchor=west] at (4.7,0.85) {one call pops a run};
  % the invariant statement
  \node[lbl, anchor=west] at (-2.0,-1.45) {an item leaves the stack at most once, so pops never exceed pushes};
\end{tikzpicture}
$$

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.

::impl{algo="multipop_stack"}

## 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.[^erickson-tax]

The one rule that makes this a valid proof:

> **Invariant (no overdraft).** The total credit stored in the structure must
> never go negative. Equivalently, for every prefix of the sequence,
> $\sum \hat{c}_i \ge \sum c_i$.

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
$\textsc{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
$\mathit{size}$, the table holds exactly $\mathit{size}/2$ items, all with zero
credit (the doubling spent it). Before the next doubling can fire, another
$\mathit{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
$\mathit{size}/2$ new items cover the $\mathit{size}/2$ older items one-for-one.

> **Invariant.** Between doublings, every item inserted since the most recent
> doubling holds $2$ units of credit, and every item that was present at that
> doubling holds $0$. Total credit is never negative.

When the table fills at $\mathit{num} = \mathit{size}$, the $\mathit{size}/2$
newcomers hold $2 \cdot \mathit{size}/2 = \mathit{size}$ units — exactly the cost
of copying all $\mathit{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.

$$
% caption: The accounting invariant mid-sequence: capacity $8$, six items. Items $1$-$4$
%          were copied by the last doubling and hold no credit; items $5$ and $6$ arrived
%          after it and hold $2$ credits apiece (dots). When items $7$ and $8$ arrive, the
%          four newcomers will hold $8$ credits in total: exactly the bill for copying
%          all $8$ items into the next block.
\begin{tikzpicture}[
  font=\footnotesize,
  cell/.style={draw, minimum width=10mm, minimum height=8mm},
  lbl/.style={font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-0.9,-1.8) rectangle (9.4,2.0);
  % items copied at the last doubling (no credit)
  \foreach \x/\v in {0/1, 1/2, 2/3, 3/4} {
    \node[cell, fill=acc!8] at (\x,0) {\v};
  }
  % items inserted since the doubling, 2 credit dots each
  \foreach \x/\v in {4/5, 5/6} {
    \node[cell, fill=acc!25] at (\x,0) {\v};
    \fill[acc] (\x-0.15,0.62) circle (0.09);
    \fill[acc] (\x+0.15,0.62) circle (0.09);
  }
  % free slots
  \node[cell] at (6,0) {};
  \node[cell] at (7,0) {};
  \node[lbl, anchor=south] at (6.5,0.55) {free slots};
  \node[lbl, acc, anchor=south] at (4.5,1.05) {2 credits per item};
  % group brackets
  \draw[black] (-0.42,-0.75) -- (-0.42,-0.95) -- (3.42,-0.95) -- (3.42,-0.75);
  \node[lbl, anchor=north] at (1.5,-1.05) {already copied: no credit};
  \draw[acc] (3.58,-0.75) -- (3.58,-0.95) -- (5.42,-0.95) -- (5.42,-0.75);
  \node[lbl, acc, anchor=north] at (4.5,-1.05) {inserted since};
\end{tikzpicture}
$$

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 $\textsc{Increment}$, which adds $1$. The cost of an increment is the
number of bits it flips.

```algorithm
caption: $\textsc{Increment}(A)$ — add one to the binary counter $A[0..k-1]$
number: 3
$i \gets 0$
while $i < k$ and $A[i] = 1$ do
  $A[i] \gets 0$ // flip a trailing 1 down to 0 (carry)
  $i \gets i + 1$
if $i < k$ then
  $A[i] \gets 1$ // set the first 0 bit
return
```

A single increment can flip many bits: incrementing $0111$ to $1000$ flips four.
In the worst case ($\,\underbrace{1\cdots1}_{k}\to\underbrace{0\cdots0}_{k}\,$,
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 $\textsc{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.

$$
% caption: Accounting for the binary counter. Each $\textsc{Increment}$ is charged
%          $2$ units: it sets one bit from $0$ to $1$, banking $1$ credit on that bit
%          (solid blue), and every $1 \to 0$ flip in a carry (outlined blue) is paid from
%          the credit already stored on that bit. Rows show the counter after each of the
%          first four increments: $001, 010, 011, 100$.
\begin{tikzpicture}[
  bit/.style={draw, minimum size=8mm, font=\small},
  set/.style={draw, minimum size=8mm, font=\small, fill=acc!28},
  carry/.style={draw=acc, minimum size=8mm, font=\small, fill=acc!8},
  lbl/.style={font=\footnotesize},
  capt/.style={font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-1.6,-1.0) rectangle (8.0,3.4);
  % row labels: counter value after the increment
  \node[lbl, anchor=east] at (-0.4,2.6) {$1$};
  \node[lbl, anchor=east] at (-0.4,1.7) {$2$};
  \node[lbl, anchor=east] at (-0.4,0.8) {$3$};
  \node[lbl, anchor=east] at (-0.4,-0.1) {$4$};
  % value 000 -> 001
  \node[bit] at (0,2.6) {0};
  \node[bit] at (0.85,2.6) {0};
  \node[set] at (1.7,2.6) {1};
  % value 001 -> 010
  \node[bit] at (0,1.7) {0};
  \node[set] at (0.85,1.7) {1};
  \node[carry] at (1.7,1.7) {0};
  % value 010 -> 011
  \node[bit] at (0,0.8) {0};
  \node[bit] at (0.85,0.8) {1};
  \node[set] at (1.7,0.8) {1};
  % value 011 -> 100
  \node[set] at (0,-0.1) {1};
  \node[carry] at (0.85,-0.1) {0};
  \node[carry] at (1.7,-0.1) {0};
  % legend
  \node[set] at (3.6,2.6) {};
  \node[lbl, anchor=west] at (4.0,2.6) {set, banks credit};
  \node[carry] at (3.6,1.7) {};
  \node[lbl, anchor=west] at (4.0,1.7) {carry, spends credit};
  \node[bit] at (3.6,0.8) {};
  \node[lbl, anchor=west] at (4.0,0.8) {unchanged};
  \node[capt, anchor=west] at (-1.5,-0.85) {one row per increment; low-order bit in the last column};
\end{tikzpicture}
$$

> **Theorem.** Starting from zero, $n$ $\textsc{Increment}$ operations on a
> binary counter cost $O(n)$ in total; the amortized cost per increment is $O(1)$.

> **Proof.** Charge $2$ per increment. Each increment sets exactly one bit to
> $1$, paying $1$ to flip it and banking $1$ on it. Each $1 \to 0$ flip is paid
> by the credit on that bit, which was deposited when the bit was last set. The
> stored credit equals the count of $1$-bits, which is $\ge 0$ always, so no
> operation overdraws. By the definition of amortized cost, $\sum c_i \le \sum
> \hat{c}_i = 2n$, hence $O(n)$ total and amortized $O(1)$. $\qed$

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

$$
\sum_{i=0}^{\lfloor \lg n \rfloor} \left\lfloor \frac{n}{2^{\,i}} \right\rfloor
\;<\; n \sum_{i=0}^{\infty} \frac{1}{2^{\,i}}
\;=\; 2n,
$$

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.

$$
% caption: Aggregate view of $n = 16$ increments: bit $i$ flips $\lfloor n / 2^{i}
%          \rfloor$ times, so the flip counts halve across the columns and the total is
%          a geometric series, $16 + 8 + 4 + 2 + 1 = 31 < 2n$ — not the naive
%          $n \cdot k$.
\begin{tikzpicture}[font=\footnotesize, lbl/.style={font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-0.6,-1.5) rectangle (7.6,4.0);
  % bars: height 0.2 per flip
  \foreach \x/\h/\c in {0/3.2/16, 1.4/1.6/8, 2.8/0.8/4, 4.2/0.4/2, 5.6/0.2/1} {
    \draw[draw=acc, fill=acc!12, line width=0.8pt] (\x,0) rectangle (\x+0.9,\h);
    \node[lbl, acc, anchor=south] at (\x+0.45,\h+0.07) {\c};
  }
  % bit labels
  \node[lbl, anchor=north] at (0.45,-0.15) {bit 0};
  \node[lbl, anchor=north] at (1.85,-0.15) {bit 1};
  \node[lbl, anchor=north] at (3.25,-0.15) {bit 2};
  \node[lbl, anchor=north] at (4.65,-0.15) {bit 3};
  \node[lbl, anchor=north] at (6.05,-0.15) {bit 4};
  % baseline
  \draw[black] (-0.3,0) -- (6.9,0);
  % total annotation
  \node[lbl, anchor=west] at (-0.5,-1.15) {altogether: 16 + 8 + 4 + 2 + 1 = 31, less than 2n = 32};
\end{tikzpicture}
$$

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.

::impl{algo="binary_counter"}

## 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.

> **Definition (potential).** Let $D_i$ be the data structure after the $i$-th
> operation, with $D_0$ the initial state. A **potential function** $\Phi$ maps
> each state to a real number with $\Phi(D_i) \ge \Phi(D_0)$ for all $i$
> (usually $\Phi(D_0) = 0$ and $\Phi \ge 0$). The **amortized cost** of the
> $i$-th operation is
> $$
> \hat{c}_i \;=\; c_i + \Phi(D_i) - \Phi(D_{i-1}).
> $$

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

$$
\sum_{i=1}^{m} \hat{c}_i
= \sum_{i=1}^{m}\parens{c_i + \Phi(D_i) - \Phi(D_{i-1})}
= \sum_{i=1}^{m} c_i + \Phi(D_m) - \Phi(D_0).
$$

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":

$$
\Phi(T) \;=\; 2\cdot T.\mathit{num} - T.\mathit{size}.
$$

Right after a doubling the table is half full ($\mathit{num} = \mathit{size}/2$
before the pending insert lands), so $\Phi$ is small; just before the next
doubling it is completely full ($\mathit{num} = \mathit{size}$), so
$\Phi = \mathit{num}$ — exactly enough banked potential to pay for copying all
$\mathit{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.

$$
% caption: The potential $\Phi = 2\,\mathit{num} - \mathit{size}$ over the first $18$
%          inserts, drawn exactly. Each cheap insert raises $\Phi$ by $2$; when the table
%          fills ($\mathit{num} = \mathit{size}$, the peaks at $4$, $8$, $16$), the next
%          insert doubles the block and $\Phi$ falls back to $2$. The height of each fall
%          is the potential the copy consumes, so the doubling's amortized cost stays at
%          $3$ like everyone else's.
\begin{tikzpicture}[
  >={Stealth[length=2.4mm]},
  lbl/.style={font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-1.0,-1.1) rectangle (12.0,4.5);
  % axes
  \draw[->] (0,0) -- (9.6,0) node[lbl, right] {items inserted};
  \draw[->] (0,0) -- (0,3.8);
  \node[lbl, anchor=south] at (0,3.85) {potential};
  % y ticks: 0.2 per unit
  \foreach \y/\v in {0.4/2, 1.6/8, 3.2/16} {
    \draw (-0.08,\y) -- (0.08,\y);
    \node[lbl, anchor=east] at (-0.14,\y) {\v};
  }
  % x ticks: 0.5 per insert
  \foreach \x/\v in {2.0/4, 4.0/8, 8.0/16} {
    \draw (\x,-0.08) -- (\x,0.08);
    \node[lbl, anchor=north] at (\x,-0.14) {\v};
  }
  % exact potential: (num, 2 num - size) scaled by (0.5, 0.2)
  \draw[acc, line width=1.6pt]
    (0,0) -- (0.5,0.2) -- (1.0,0.4) -- (1.5,0.4) -- (2.0,0.8)
          -- (2.5,0.4) -- (3.0,0.8) -- (3.5,1.2) -- (4.0,1.6)
          -- (4.5,0.4) -- (5.0,0.8) -- (5.5,1.2) -- (6.0,1.6)
          -- (6.5,2.0) -- (7.0,2.4) -- (7.5,2.8) -- (8.0,3.2)
          -- (8.5,0.4) -- (9.0,0.8);
  % peak markers where the table is full
  \node[lbl, acc, anchor=south] at (2.0,0.86) {full};
  \node[lbl, acc, anchor=south] at (4.0,1.66) {full};
  \node[lbl, acc, anchor=south] at (8.0,3.26) {full};
  % annotation below the axis
  \node[lbl, anchor=west] at (0.15,-0.75) {a doubling spends the built-up potential: it falls back to 2};
\end{tikzpicture}
$$

> **Theorem.** With $\Phi(T) = 2\,T.\mathit{num} - T.\mathit{size}$, every
> $\textsc{Table-Insert}$ has amortized cost at most $3$. Hence $n$ inserts into
> an initially empty table run in $O(n)$ time.

> **Proof.** Let $\mathit{num}_i$ and $\mathit{size}_i$ be the values after the
> $i$-th insert, and write $\Phi_i = 2\,\mathit{num}_i - \mathit{size}_i$. In
> every case $\mathit{num}_i = \mathit{num}_{i-1} + 1$.
>
> **Case A: no doubling.** Here $\mathit{size}_i = \mathit{size}_{i-1}$ and
> $c_i = 1$. The amortized cost is
> $$
> \hat{c}_i = c_i + \Phi_i - \Phi_{i-1}
> = 1 + \parens{2\,\mathit{num}_i - 2\,\mathit{num}_{i-1}}
> = 1 + 2 = 3.
> $$
>
> **Case B: doubling.** The table was full before this insert, so
> $\mathit{num}_{i-1} = \mathit{size}_{i-1}$, the copy costs $\mathit{num}_{i-1}$,
> and $c_i = \mathit{num}_{i-1} + 1$. The size doubles:
> $\mathit{size}_i = 2\,\mathit{size}_{i-1} = 2\,\mathit{num}_{i-1}$. Then
> $$
> \begin{aligned}
> \hat{c}_i &= c_i + \Phi_i - \Phi_{i-1} \\
> &= (\mathit{num}_{i-1} + 1)
>   + \parens{2\,\mathit{num}_i - \mathit{size}_i}
>   - \parens{2\,\mathit{num}_{i-1} - \mathit{size}_{i-1}} \\
> &= (\mathit{num}_{i-1} + 1)
>   + \parens{2(\mathit{num}_{i-1}+1) - 2\,\mathit{num}_{i-1}}
>   - \parens{2\,\mathit{num}_{i-1} - \mathit{num}_{i-1}} \\
> &= (\mathit{num}_{i-1} + 1) + 2 - \mathit{num}_{i-1} = 3.
> \end{aligned}
> $$
>
> In both cases $\hat{c}_i \le 3$. Summing, $\sum c_i \le \sum \hat{c}_i \le 3n$,
> and since $\Phi_0 = 0$ and $\Phi \ge 0$, this bounds the true total by $O(n)$.
> $\qed$

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 $\mathit{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:

$$
\Phi(A) \;=\; \text{the number of } 1\text{-bits in } A.
$$

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

$$
\hat{c}_i \;=\; c_i + \Phi_i - \Phi_{i-1}
\;=\; (t_i + 1) + (1 - t_i)
\;=\; 2,
$$

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.

> **Remark (why double, not add a constant).** Growing by a _fixed_ increment $c$
> instead of doubling breaks the bound. Then the $j$-th reallocation copies
> $\approx jc$ items, and over $n$ inserts the copies sum to
> $c + 2c + \dots \approx \Theta(n^2/c)$ — amortized $\Theta(n)$ per insert, not
> $O(1)$. _Geometric_ growth (any factor $> 1$) is what makes the copy work
> telescope to a constant, and that is why real dynamic arrays double.

$$
% caption: Why geometric growth wins. Doubling spaces the reallocations exponentially, so
%          the copy sizes $1, 2, 4, 8, \ldots$ sum to less than $2n$ (amortized $O(1)$).
%          Adding a fixed increment reallocates every $c$ inserts, copying $c, 2c, 3c,
%          \ldots$, which sums to $\Theta(n^2 / c)$ (amortized $\Theta(n)$).
\begin{tikzpicture}[
  font=\footnotesize, >={Stealth[length=2.2mm]},
  lbl/.style={font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \useasboundingbox (-2.7,-2.7) rectangle (10.4,1.1);
  % doubling row: ticks at 1,2,4,8 along a line
  \node[lbl, anchor=east] at (-0.2,0.5) {doubling};
  \draw[acc, line width=1pt] (0,0.5) -- (8.6,0.5);
  \foreach \x/\lab in {0.5/1, 1.5/2, 3.5/4, 7.5/8} {
    \draw[acc, line width=1.4pt] (\x,0.35) -- (\x,0.65);
    \node[lbl, acc, anchor=south] at (\x,0.7) {\lab};
  }
  \node[lbl, anchor=west] at (8.8,0.5) {sparse};
  % increment row: ticks every c inserts
  \node[lbl, anchor=east] at (-0.2,-1.6) {add a constant};
  \draw[acc!55, line width=1pt] (0,-1.6) -- (8.6,-1.6);
  \foreach \x in {0.7,1.4,2.1,2.8,3.5,4.2,4.9,5.6,6.3,7.0,7.7,8.4} {
    \draw[acc!55, line width=1.4pt] (\x,-1.75) -- (\x,-1.45);
  }
  \node[lbl, anchor=west] at (8.8,-1.6) {dense};
  % labels (plain prose; precise sums live in the caption)
  \node[lbl, acc, anchor=west] at (0,-0.3) {few resizes, copies stay small};
  \node[lbl, anchor=west] at (0,-2.4) {many resizes, ever-larger copies};
\end{tikzpicture}
$$

::impl{algo="dynamic_array"}

## Choosing a method

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

> **Remark.** They are interchangeable in power but not in ergonomics:
> - **Aggregate** — easiest when a single global count bounds the total
>   (multipop: pops $\le$ pushes; the array: one geometric sum). One amortized
>   cost for all operations.
> - **Accounting** — best when you can pin saved work onto concrete elements
>   (a credit per $1$-bit, two credits per un-copied item). Different charges per
>   operation type; verify credit never goes negative.
> - **Potential** — most flexible and the standard tool for complex structures.
>   Encodes saved work in one function $\Phi$; the hard part is _finding_ a $\Phi$
>   that makes the algebra collapse.

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 = 2\,\mathit{num} - \mathit{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**](/algorithms/data-structures/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**](/algorithms/data-structures/hash-tables). A hash table that
  doubles (and halves) its bucket array to keep the load factor bounded uses
  exactly the $\textsc{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.[^skiena-dyn]

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.[^okasaki] 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.[^sleator-tarjan] 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 + \dots < 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 = 2\,\mathit{num} - \mathit{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](/algorithms/data-structures/union-find),
  [resizable hash tables](/algorithms/data-structures/hash-tables), and every
  dynamic array.

[^clrs-amort]: **CLRS**, _Introduction to Algorithms_, Ch. 16 — Amortized Analysis: the aggregate, accounting, and potential methods, with the multipop stack, binary counter, and dynamic table as the chapter's running examples.
[^erickson-tax]: **Erickson**, _Algorithms_ — the amortized-analysis chapter frames the accounting method as taxation and derives the potential method from it; the binary counter and multipop stack appear there in the same roles.
[^skiena-dyn]: **Skiena**, _The Algorithm Design Manual_, §3.4 — Dynamic Arrays: the doubling construction and its amortized $O(1)$ append.
[^okasaki]: Okasaki, C. (1998). _Purely Functional Data Structures_. Cambridge University Press — lazy evaluation and scheduling to make amortized bounds hold under persistence; the banker's and physicist's methods.
[^sleator-tarjan]: Sleator, D. D. & Tarjan, R. E. (1985). "Self-adjusting binary search trees." _Journal of the ACM_ 32(3) — splay trees and the potential argument for $O(\log n)$ amortized operations; Sleator & Tarjan (1985), "Amortized efficiency of list update and paging rules," _CACM_ 28(2), on competitive analysis.