Amortized: the expensive step you almost never take

Every operation is $O(1)$ except one, which is $O(n)$, and the structure is still honestly $O(1)$. That sentence makes the site’s Queue with Two Stacks problem sound like a magic trick. It is also the exact meaning of amortized, which the problem description uses without ceremony: “Aim for amortised $O(1)$ per operation.” This article explains the term: how a structure can contain an operation that shuffles every element it holds and still earn a constant-time label, how to count the cost honestly, and when the amortized promise is the guarantee you need—and when it is not. The hash-tables article met the word once, in the resize story. This is the full treatment.

The queue from two stacks

The problem gives you an awkward constraint: build a FIFO queue—first in, first out—using exactly two stacks, where a stack only lets you touch the top. The stacks and queues article covers the shapes themselves. The trick is getting the order back. Keep one stack, the inbox, for pushes. A push prepends, so the newest element is on top and the oldest is at the bottom—exactly backward from what a queue wants to pop. Keep a second stack, the outbox, for pops. When the outbox is empty, transfer the entire inbox into it. Reversing the inbox puts the oldest element on top of the outbox, where a pop can reach it. From then on, pops read the outbox top—the queue front—in order until the outbox is empty again. The encoding article names the general lesson: the queue is the concept, the two stacks are the representation, and the transfer is where the representation shows itself.

The surprise is in that transfer. Most pops are cheap because the outbox already holds the front. The first pop after a long run of pushes is different: the outbox is empty, so the transfer reverses every element in the inbox. Push a hundred thousand values, then that one pop moves all hundred thousand. The operation is $O(n)$ in the worst case, and the worst case really happens. The claim “$O(1)$ per operation” looks like a lie.

The accounting

Count what each element does. Every value that enters the queue moves exactly three times over its whole life: once onto the inbox, once from the inbox to the outbox during the transfer, and once off the outbox when it is popped. That is three $O(1)$ moves per element, regardless of how the operations are interleaved. The expensive transfer is not new work; it is the second move of every element in the inbox, done all at once instead of one per operation. The $O(n)$ pop is the sum of $n$ deferred $O(1)$ moves, and each move was already owed.

Make the accounting literal. Charge every push two units of work instead of one: one unit pays for the push, and one unit goes into a bank for the element’s future transfer. The transfer then costs nothing new; the pushes that put the elements there fund it. With that bookkeeping, every push costs two units, every pop costs one, and the account never runs a deficit. An element cannot be transferred before it was pushed. The $O(n)$ spike is $n$ previously paid units arriving at once, so every operation is $O(1)$ by construction. This is the charging method, the simplest of the amortized-analysis techniques, and it contains the whole argument.

The numbers make the average visible. Run a hundred thousand pushes followed by a hundred thousand pops, counting element moves:

defmodule Queue do
  @moduledoc "FIFO queue from two stacks; pop returns {front, queue, moves}."
  def new, do: {[], []}

  # push onto the inbox (newest first)
  def push({inbox, outbox}, value), do: {[value | inbox], outbox}

  # a normal pop reads the outbox head - one move
  def pop({inbox, [head | rest]}), do: {head, {inbox, rest}, 1}
  def pop({[], []}), do: raise "empty"

  # a transfer pop reverses the whole inbox into the outbox first -
  # every element moves once, then the head is read
  def pop({inbox, []}) do
    [head | rest] = Enum.reverse(inbox)
    {head, {[], rest}, length(inbox) + 1}
  end
end

n = 100_000
q = Enum.reduce(1..n, Queue.new(), fn i, q -> Queue.push(q, i) end)

{_q, pop_moves} =
  Enum.reduce(1..n, {q, 0}, fn _, {q, acc} ->
    {_front, q2, moves} = Queue.pop(q)
    {q2, acc + moves}
  end)

total_moves = n + pop_moves

# ops: 200000, total moves: 300000, avg per op: 1.5
IO.puts("average moves per operation: #{total_moves / (2 * n)}")
# the first pop transferred 100000 elements in one go
IO.puts("most expensive single operation: #{n + 1} moves")

The output puts the amortized claim in numbers: 1.5 moves per operation on average over the whole sequence, and one operation that cost 100,001 moves by itself. Both numbers are true. The average is not a hope about typical inputs: this workload is the adversarial worst case, every push followed by the single pop that pays for all of them. The average stays flat because the cheap operations paid for the expensive one. That is what “amortized” adds to plain “average”: the guarantee applies to the sequence, even when an adversary chooses the worst possible order of operations.

Amortized is not average-case

Draw this distinction sharply. There are three different things $O(1)$ can mean, and only one is amortized. A worst-case $O(1)$ operation is bounded on every call: array indexing, a hash lookup on a perfect table, the top of a stack. No input or history can make it slow, and the guarantee holds one operation at a time. An average-case $O(1)$ operation is bounded on typical inputs, such as a hash lookup when the hashes scatter evenly. An adversary can violate that guarantee: a hash function can collide, and lookups then degrade. Average-case claims therefore carry an unstated “assuming the input cooperates.” An amortized $O(1)$ operation is bounded over every sequence: no matter what order the operations arrive in, the total cost of any $n$ operations is $O(n)$. Individual operations may be arbitrarily expensive. The sequence never is.

The three labels are easy to confuse. The two-stack queue shows the difference. Its pop is not worst-case $O(1)$ because the transfer pop is $O(n)$. It is not average-case $O(1)$ in the “random inputs” sense either; the analysis never mentioned randomness. It worked for the adversarial sequence of all-pushes-then-all-pops. It is amortized $O(1)$: the total over any sequence is linear because the charging argument works for every possible sequence, not the likely ones. The hash-tables article’s resize story has the same shape at one level up: the inserts that filled the table fund the expensive rehash, so the sum over any sequence of inserts is linear even though a single insert can touch every element. Both structures earn their constant-time label the same way. The rare expensive step is not a violation of the promise; it is the promise’s bill arriving, and the cheap steps before it already paid.

When the promise is enough

Ask what you are measuring. If you are optimizing a total—a batch of a million operations, the work of an algorithm over a whole input, or the average latency of a long-running service—amortized $O(1)$ is as good as worst-case $O(1)$ because only the sum matters, and the sum is bounded. Most algorithm exercises live here. That is why the problem page can say “Aim for amortised $O(1)$ per operation” and mean a real contract: any correct sequence of operations, however hostile, finishes in linear total time.

If you are optimizing one operation’s latency, the promises part ways. The transfer pop is where you feel it. A queue feeding a user interface, a request handler, or a real-time loop cannot necessarily absorb one operation that moves a hundred thousand elements while the user waits. The average may be flat; the frame that stalls is still stalled. When worst-case latency for one operation matters, use a structure with no transfer to hide: the encoding article covers the queue-as-ring, whose head and tail move by index arithmetic and whose every operation is worst-case $O(1)$. The two-stack queue and the ring buffer implement the same concept with different promises. That difference is precisely the word this article is about. When you read a complexity claim, ask which guarantee the problem needs. The What O(n) article made that point about growth shapes, and the same discipline applies to amortized analysis: name the promise, then check it against what you are building. The Algorithms past the interview article calls the passing mention of “amortized” interview vocabulary. This is the concept the word exists for.

Where to go next

• Queue with Two Stacks - implement the transfer yourself: get the FIFO order exactly right, and meet the amortized claim as a problem statement instead of prose.
• Hash tables: the O(1) that has fine print
  • the resize story is the same accounting one level up: the rare rehash funded by the inserts that filled the table.
• The encoding: how complex structures hide in simple ones
  • the queue-as-ring, the worst-case $O(1)$ sibling whose operations are bounded one at a time.
• Stacks, queues, and associative arrays
  • the shapes this article’s two-stack trick is built from, and the discipline that a queue is a queue whatever the representation.
• What O(n) actually promises - the growth shapes, and the habit of asking which guarantee a promise actually makes.
• Algorithms past the interview
  • where the word “amortized” first appears on this site, in passing; now you have the concept behind it.

The two-stack queue is honestly $O(1)$ in the same way a bank account can honestly handle a large withdrawal: the money was deposited in advance, and the balance never went negative. Amortized analysis keeps the books that way. Charge each element for the work it will eventually cause, and the expensive step is neither a surprise nor a lie. The average is not a hope about the input; it is a proof about every sequence. One operation in a hundred thousand may move a hundred thousand elements, and the structure is still constant-time because that operation was paid for a hundred thousand times over, one cheap operation at a time.