Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 225 ยท Analyzing Algorithms

Amortized Analysis

Learn amortized analysis with dynamic arrays, binary counters and multipop stacks. Aggregate, accounting and potential methods explained step by step.

You have probably been told that list.append in Python is O(1). Yet sometimes an append is slow: when the list runs out of room, Python must allocate a bigger block of memory and copy every existing item into it, which costs O(n). So which is it?

Both statements are true, and amortized analysis is the tool that reconciles them. Instead of asking how much a single operation costs in the worst case, it asks: if I perform a whole sequence of operations, what is the average cost per operation? The key point is that this is a guarantee about the sequence, not a bet on random luck. That makes it different from the average case, which averages over inputs.

The idea in one picture

Imagine saving up for an expensive purchase. Most days you spend nothing and put a coin in a jar. Occasionally you pay a large bill, but the jar already holds enough coins to cover it. Spread over many days, your daily cost is small and steady.

TEXT
operation:   1   2   3   4   5   6   7   8   9  ...
cost:        1   1   1   1   1   1   1   1   9  ...   <- rare expensive step
                                          \_ paid for by earlier cheap steps
amortized:   about 2 per operation

Amortized cost = (total cost of any sequence of n operations) / n. If that is O(1), we say the operation is amortized O(1), even though a few individual steps cost much more.

The dynamic array

A Python list is a dynamic array: a block of memory with some spare capacity. Appending when there is room is a single write. When the block is full, the list allocates a larger block, copies everything over and then appends. (The next lessons on arrays and dynamic arrays build one from scratch.)

The growth rule is what makes this fast. Here is a simplified array that doubles its capacity and counts every element it copies:

Python Appending with capacity doubling

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Most appends cost 1. The cost spikes at positions 2, 3, 5, 9 and 17 (counting from 1), exactly when the array is full, and each spike is about as large as the current size. But the spikes get rarer as fast as they get bigger. For a thousand appends, the total is about 2n, so the average cost is a small constant.

Method 1: aggregate analysis

The aggregate method adds up the true cost of a whole sequence and divides by n. With doubling, the resizes happen when the size is 1, 2, 4, 8, ..., up to at most n, and each copies that many items:

TEXT
total copies  โ‰ค  1 + 2 + 4 + 8 + ... + n/2 + n  <  2n
total cost    =  n writes + (copies)  <  3n
amortized     =  total / n  <  3  ->  O(1)

The geometric series 1 + 2 + 4 + ... is always less than twice its last term. That single fact is the heart of why doubling works.

Why the growth rule matters

What if the array grew by a fixed amount, say 10 slots, instead of doubling? Then resizes happen every 10 appends, each copying everything so far, and the total is 10 + 20 + 30 + ... which is quadratic. Compare the two strategies directly:

Python Growth by doubling vs by a constant

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Doubling grows linearly with n while the "+10" strategy grows quadratically. Multiplying the capacity by any constant factor greater than 1 (real implementations use factors like 1.125 or 1.5 in some languages) keeps the total linear. Adding a constant does not.

Method 2: the accounting (banker's) method

The accounting method gives each operation a fixed charge. Cheap operations are charged more than they cost, and the leftover is saved as credit on the data structure. Expensive operations are paid for with saved credit. If the credit never goes negative, the charge is a valid amortized cost.

For the dynamic array, charge 3 coins per append: 1 pays for the write; 2 are saved. When a doubling happens at size s, the s/2 items added since the last resize each saved 2 coins, which is s coins, enough to pay for copying all s items.

Python Banker's method: the credit never goes negative

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The balance never drops below zero, so charging 3 per append is enough, and therefore appending is amortized O(1). (You can check that charging 2 would not work: the balance would go negative.)

Method 3: the potential method

The potential method is the accounting method in mathematical clothing. You define a number called potential ฮฆ for the current state of the data structure, which stands for stored-up work. The amortized cost of an operation is its actual cost plus the change in potential:

TEXT
amortized cost = actual cost + ฮฆ(after) - ฮฆ(before)

For the dynamic array a good choice is ฮฆ = 2 ร— size โˆ’ capacity. Right after a resize it is near 0; just before the next one it is about size, which is exactly enough to pay for the copy. You do not need to prove potentials in an interview, but it helps to know that they exist: they are how textbooks analyze trickier structures such as union-find and the heaps in advanced amortized structures.

Example: the binary counter

Counting upward in binary flips a variable number of bits. Going from 0111 to 1000 flips four bits, but going from 1000 to 1001 flips only one.

TEXT
0000 -> 0001   1 flip
0001 -> 0010   2 flips
0010 -> 0011   1 flip
0011 -> 0100   3 flips   <- carry chain

A single increment can flip up to k bits (k = number of bits), so the worst case is O(k). But amortized?

Python Binary counter: total bit flips

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Bit 0 flips on every increment, bit 1 on every second, bit 2 on every fourth, and so on. So over n increments the total is n + n/2 + n/4 + ... < 2n. The average per increment never exceeds 2, even though one unlucky step flipped ten bits.

Example: a stack with multipop

Suppose a stack supports push(x) in O(1) and multipop(k) which pops up to k items. A single multipop can take O(n), so a naive analysis of n operations says O(nยฒ). But every item can be popped only after it was pushed, and only once. In any sequence of n operations, the total number of pops is at most the number of pushes, which is at most n.

Python Multipop: pops are limited by pushes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Total work is at most 2n, so the amortized cost per operation is O(1). Mind how this argument works: it counts pops against pushes, a form of the aggregate method. You will use the same argument for the monotonic stack in monotonic stack and for sliding-window algorithms such as those in sliding window, where each pointer moves forward at most n times.

Amortized vs average vs worst

Average case Amortized
Averages over possible inputs (needs a distribution) a sequence of operations on one structure
Depends on luck? yes, on the assumed distribution no, it is a worst-case guarantee for the sequence
Example quicksort on random input list.append

An amortized O(1) operation can still be slow once in a while. If you need every single operation to be fast (a game frame loop, a network router), amortized bounds are not enough, and you want a worst-case O(1) structure instead.

Common mistakes

  • Treating amortized as average. There is no probability involved. It is a bound on total work.
  • Forgetting the sequence assumption. The guarantee holds over operations starting from an empty (or fresh) structure. Mixing in deletions can break it: if an array both doubles when full and halves when half empty, alternating operations at the boundary can thrash. Real implementations use different thresholds to prevent this.
  • Using a constant growth increment. Resizing by "+k" makes the total quadratic.
  • Claiming O(1) for single operations. The right words are "amortized O(1)".

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is list.append amortized O(1) even though a resize costs O(n)?

    With geometric growth the copy sizes form a series like 1 + 2 + 4 + ... that sums to less than 2n, so n appends cost O(n) in total.
  2. 2. What happens to the total copying cost if the array grows by a fixed +10 slots instead of doubling?

    A resize every 10 appends, each copying all existing items, gives 10 + 20 + 30 + ... which is proportional to nยฒ.
  3. 3. In the accounting method, what makes a charge per operation valid?

    If the credit balance never goes below zero, the charges always cover the true costs, so the charge is an upper bound on the amortized cost.
  4. 4. A binary counter has k bits. What is the amortized number of bit flips per increment over n increments?

    Bit i flips only every 2^i increments, so the total is below 2n and the average is at most 2 flips per increment.
  5. 5. How does amortized cost differ from average-case cost?

    Average-case analysis needs an assumed input distribution. Amortized analysis bounds the total cost of any operation sequence.

Summary

  • Amortized analysis bounds the average cost per operation over a sequence, guaranteed with no probabilities.
  • Dynamic arrays double their capacity, so resizes cost 1 + 2 + 4 + ... < 2n in total and append is amortized O(1).
  • Growing by a constant amount instead of a factor makes the total quadratic.
  • Three methods: aggregate (total divided by n), accounting (charge extra, bank credit) and potential (a function of the state).
  • Binary counters and multipop stacks are classic examples: expensive steps are paid for by many cheap ones.
  • A single amortized-O(1) operation can still be slow occasionally; use a worst-case bound when that matters.

Next: Recurrences and the Master Theorem