What is amortized analysis? | Interview Question

Q: What is amortized analysis?

**Target Audience:** Interview candidates who know [Big-O notation](/interview-question/what-is-big-o-notation) and want to understand why "occasionally slow" operations can still be O(1). **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** Each idea is explained in plain words first, then tagged with `📌 Interview term:` so you also learn the exact vocabulary an interviewer expects. Every count on this page comes from running the Python code shown, and the **Verified** section quotes that output; library behaviour is either measured or cited. ## 1. Why This Even Matters — A Story First You collect books. They live on a bookshelf, and when the shelf is full you buy one twice as big and carry every book across. Moving day is miserable: the day you go from 512 to 1,024 slots, you carry 512 books. But look at the whole year. You moved 1 book, then 2, then 4, then 8 … then 512. Add them up: 1,023 moves for 1,024 books, **less than one move per book**. Most days yo

The problem

Question presented to candidate: "Appending to a dynamic array sometimes has to copy every element into a bigger block, which is O(n). Yet everyone says append is O(1). Explain how both can be true, what amortized analysis is, and show it for the Python structures you would use."

What a strong answer should cover:

Amortized cost = total cost of a worst-case sequence of n operations, divided by n; it is a guarantee, not an average over random inputs.
The doubling argument: copies 1 + 2 + 4 + … < 2n, so n appends cost under 3n — O(1) amortized, while a single append is still O(n) in the worst case.
Why the growth must be geometric: growing by a constant amount gives O(n²) total; shrinking must leave a gap (shrink at ¼ full, not ½) or it thrashes.
The three methods by name (aggregate, accounting/banker, potential) and another example such as a queue built from two stacks.
Python specifics: list.append is amortized O(1) while list.pop(0) is O(n) every call; CPython over-allocates by roughly an eighth, which is still a geometric growth factor.

Clarifying questions expected:

"Do we care about the worst case of a single operation (latency), or only total throughput?"
"Do we know the final size in advance, so we could pre-allocate?"

Code / implementation expected: Optional — a Python dynamic array or a two-stack queue that counts copies, with the amortized argument stated.

amortized

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Interview candidates who know Big-O notation and want to understand why "occasionally slow" operations can still be O(1). Difficulty: Medium Language: Python 3

How to read this doc: Each idea is explained in plain words first, then tagged with 📌 Interview term: so you also learn the exact vocabulary an interviewer expects. Every count on this page comes from running the Python code shown, and the Verified section quotes that output; library behaviour is either measured or cited.

1. Why This Even Matters — A Story First

You collect books. They live on a bookshelf, and when the shelf is full you buy one twice as big and carry every book across. Moving day is miserable: the day you go from 512 to 1,024 slots, you carry 512 books.

But look at the whole year. You moved 1 book, then 2, then 4, then 8

The solution is hidden so you can try first

11 min read · 13 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonDynamic array: cost of every push, doubling vs growing by a constant

Practice

PythonQueue from two stacks: one slow dequeue, O(1) amortized

Practice

PythonWhy shrinking at half full breaks the bound

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.