What is amortized time complexity
What is amortized time complexity? It is the cost per operation averaged over a worst-case sequence, which is why a dynamic array append is O(1) even though some appends copy the whole array. Here is the arithmetic, with real numbers.
What is amortized time complexity? It is the average cost per operation over a worst-case sequence of operations, not over random inputs. A dynamic array append costs O(n) occasionally but O(1) amortized, because expensive resizes are rare enough that spread across all appends they add only a constant per call.
That one sentence is the whole idea, but most people who read it nod and then still cannot say why the bound holds, or when it quietly stops holding. This essay does the arithmetic with concrete numbers, shows three other places the same argument appears, and ends with the cases where an amortized guarantee is not the guarantee you actually need.
How does a dynamic array append get to O(1) amortized?
It works because the array doubles its capacity when it fills, so the total copying across n appends is a geometric series that sums to less than 2n. Each individual append is either a cheap write or a rare, expensive copy, and the expensive ones get exponentially further apart.
Take a concrete run. Start with an empty array of capacity 1 and append 1,000,000 elements, doubling whenever the array is full. A resize happens when the size equals the capacity, and it copies every existing element into a fresh block. The resizes therefore copy 1, 2, 4, 8, and so on, up to 524,288 elements, which is 219. The last resize happens when the array holds 524,288 items and needs to take the 524,289th. After that the capacity is 1,048,576, which is enough for the rest of the run.
The total copy count is 1 + 2 + 4 + ... + 524,288 = 220 minus 1 = 1,048,575. Add the 1,000,000 plain writes and the whole run costs 2,048,575 element writes. Divide by a million appends and you get about 2.05 writes per append. That number is the amortized cost. It is a constant, and it does not grow if you run ten million appends instead; you would get roughly 2.1 again, not 20.
Now look at the other side. The single worst append in that run copies 524,288 elements. If you timed each call individually, you would see 999,980 calls that take nanoseconds and 20 calls that take noticeably longer, with the biggest one taking about half a million times the work of a plain write. Amortized O(1) does not claim that spike is absent. It claims the spike is paid for by everything around it.
Why does the growth factor matter so much?
The growth factor matters because the amortized bound only survives if capacity grows by a multiplicative factor; growing by a fixed amount turns the same loop into O(n) per append. The table below runs the same 1,000,000 appends under four policies.
| Growth policy | Resizes for 1,000,000 appends | Total elements copied | Amortized copies per append |
|---|---|---|---|
| Add 1 slot each time | about 1,000,000 | about 500,000,000,000 | about 500,000 |
| Add 1,000 slots each time | about 1,000 | about 500,000,000 | about 500 |
| Multiply by 1.5 | about 34 | between 2,000,000 and 3,000,000 | 2 to 3 |
| Multiply by 2 | 20 | 1,048,575 | about 1.05 |
The first two rows are the instructive ones. Adding 1,000 slots feels generous, and for an array of a few thousand items it is fine. But the number of resizes is n divided by 1,000, and each resize copies on average n/2 items, so the total is about n2/2,000. At n = 1,000,000 that is 500 million copies, or 500 per append. The cost per append is proportional to n, only with a small constant out front. A big additive step postpones the problem; it does not remove it.
The multiplicative rows differ only by a constant. With growth factor g, the copies form a geometric series whose sum is bounded by the final size times g/(g-1). For g = 2 that is at most 2n; for g = 1.5 it is at most 3n. Real libraries pick different points on this curve. As far as I know, Java's ArrayList grows by 1.5, several C++ vector implementations double, and CPython's list over-allocates by roughly 12.5 percent plus a small constant. At 1.125 the series multiplier is 9, so Python's lists copy up to about nine elements per append in the worst phase of growth. That is still a constant, and the lower factor buys tighter memory use. The trade is more copying for less wasted space, and nothing about the asymptotics changes.
How is amortized cost different from average-case cost?
Amortized cost is a worst-case guarantee over a sequence of operations, while average-case cost is an expectation over a probability distribution of inputs. The first needs no assumptions about your data; the second depends entirely on them.
Quicksort with a random pivot has an average-case cost of O(n log n) because we assume the inputs, or the pivot choices, are well distributed. A hash table lookup is O(1) on average only if the hash function spreads keys evenly. Take away the assumption, with an adversarial key set, and the bound fails. I covered how that plays out in practice in why a hash map gets slow.
Amortized analysis makes no such assumption. Feed a dynamic array the nastiest sequence of operations you can design and the total over n appends is still under 3n element writes. There is no probability anywhere in the proof, which is the reason you can lean on it in code that handles hostile input. The guarantee is about the sum, though, not about any one call, and that distinction is where the trouble starts later in this essay.
Where else does amortized analysis show up?
It shows up wherever an expensive operation can only happen after many cheap ones have built up the work for it. Three standard cases cover most of what you will meet in interviews and in production code.
A queue built from two stacks. Push goes onto an inbox stack. Pop takes from an outbox stack, and if the outbox is empty it first moves everything from the inbox across.
class Queue:
def __init__(self):
self.inbox, self.outbox = [], []
def push(self, x):
self.inbox.append(x)
def pop(self):
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
return self.outbox.pop()Push 1,000 items and then pop once: that pop costs 1,001 steps. The next 999 pops cost one step each. Across 1,000 pushes and 1,000 pops, every element is pushed once, moved once, and popped once, so the total is a fixed number of operations per element, about four counting each stack operation. That is 4,000 steps for 2,000 queue operations, or 2 per operation, and it holds regardless of how the calls interleave. The bound works because an element can only be moved once; the inbox must refill before the next transfer.
A binary counter. Incrementing a counter flips the trailing ones to zeros and one zero to a one. Counting from 0 to 8 flips 1, 2, 1, 3, 1, 2, 1, and 4 bits on the eight increments, a total of 15, which is under 2 per increment. Bit 0 flips every time, bit 1 every second time, bit 2 every fourth, so the total over n increments is n + n/2 + n/4 + ... which stays below 2n. The worst single increment flips every bit, and it is paid for by all the quiet ones.
Two pointers and sliding windows. A window loop has a while nested inside a for, and the inner loop can run n times on a single outer iteration. Naive reading says O(n2). But the left pointer only ever moves forward and can advance at most n times in total, and the right pointer likewise, so the whole loop is at most 2n steps. That is an amortized argument wearing a different costume: a single iteration may be expensive, but you cannot do expensive iterations often. The sliding window concept page walks through the pattern, and it is the most common place interview candidates meet amortization without hearing the word.
Hash tables belong on this list as well. When the load factor crosses a threshold the table rehashes everything into a bigger bucket array, which is the same doubling argument as the dynamic array. The load factor and collisions page shows the threshold mechanics.
How do you actually prove an amortized bound?
You prove it by one of three methods: aggregate (add up the whole sequence and divide), accounting (charge each operation a fixed fee and show the savings never go negative), or potential (define a function of the data structure state that absorbs the expensive jumps). The doubling array above was the aggregate method. The accounting method needs a picture, so here is mine.
Imagine a rented flat with one bookshelf. Every time the shelf is full you buy a shelf twice the size and carry every book to it. Moving day is miserable, but you know when it will happen, and you can save for it. Charge yourself 3 coins every time you shelve a book. One coin pays for placing the book. The other two go into a jar attached to that book. When the shelf of capacity c fills and you buy one of capacity 2c, the c/2 books added since the last move each hold 2 coins, which is c coins in total, and moving c books costs c. The older books have already spent their coins; the newer ones pay for everyone. The jar never goes negative, so 3 coins per append is a valid amortized cost, and the real cost is never more than that on average.
The potential method is the same idea stated as a function: define the potential as twice the number of elements minus the capacity, show that cheap appends raise it by 2 and a resize drops it by about the cost of the copy, and the amortized cost of each operation (real cost plus change in potential) is a constant. I find the coin jar easier to hold in my head, and the potential function easier when the data structure is complicated enough that you cannot say which element owns which coin. Both give the same answer when both apply.
The common error in all three is forgetting the starting state. The accounting only works if the jar starts empty and the structure starts in a known configuration. An amortized bound is a statement about sequences from an initial state, not about an arbitrary call made on a structure someone else has already mutated.
When does amortized O(1) still hurt?
It hurts whenever one slow call matters more than the average, and whenever the structure is used in a way that breaks the sequence assumption. Three situations come up.
- Latency budgets. If a request handler appends to a list and the list needs to copy 524,288 items at that moment, that request is slow, even though the mean is excellent. For a game frame budget of 16 ms or a p99 target in a service, you may want to reserve capacity up front, or use a structure that spreads the work incrementally.
- Persistent or shared versions. The queue built from two stacks is amortized O(1) only if you use each version once. If you keep an old version in which the outbox is empty and the inbox holds 1,000 items, and pop from it repeatedly, every pop pays the full 1,001 steps again. The coins were spent the first time and cannot be spent twice. Functional-language queues need extra machinery, such as lazy evaluation, to restore the bound.
- Memory and shrinking. Doubling needs the old and new blocks alive at the same moment, so peak memory is up to 3x the live data during a resize. Shrinking policies matter too: if you halve capacity as soon as the array is half empty, alternately pushing and popping at the boundary triggers a resize on every call. The usual fix is to shrink only when the array drops to a quarter full.
This is the practical meaning of what I argued in complexity is a contract: an amortized bound is a promise about totals, and you should check whether the thing you care about is the total or the worst single call.
Frequently asked questions
Is amortized O(1) the same as average O(1)?
No. Average-case O(1) depends on a probability model of the inputs, while amortized O(1) is a worst-case guarantee on the total cost of any valid sequence of operations. You can rely on the amortized bound against adversarial input; you cannot do that with an average-case one.
Should I say O(1) or amortized O(1) in an interview?
Say amortized O(1) for dynamic array appends, hash table inserts, and stack or queue operations that sometimes trigger a bulk rebuild. Then add one sentence of reasoning, such as the doubling argument. Interviewers usually care that you know the occasional expensive call exists and why it does not dominate.
Why doesn't growing the array by a fixed 1,000 slots work?
Because the number of resizes grows linearly with n, and each resize copies a number of items that also grows with n. At 1,000,000 appends that is roughly 500 million copies, or 500 per append, so the cost per append is still proportional to n. Only a multiplicative growth factor makes the copies form a geometric series.
To see the argument at work in a real problem, take the window loop in longest substring without repeating characters, count how many times each pointer can move, and confirm the total is at most 2n.