cf.completefrontend
FOUNDATIONS · CORE

Amortized analysis

Measure the average cost of each operation over a long run, so a rare expensive step is shared by many cheap ones.

Time O(1) amortized per pushSpace O(n)2 practice problemsStep-through picture

The idea

Some operations are usually cheap but sometimes expensive. A JavaScript array's push is the classic case: most pushes just write into a free slot, but when the array is full it must get a bigger block of memory and copy every item across.

Amortized analysis looks at the total cost of many operations together, then divides by how many there were. If the expensive steps are rare enough, the average per operation is small, even though one single operation can be slow.

The trick that makes push cheap on average is doubling: when the array is full, make it twice as big. The code here is a tiny dynamic array that counts every copy, so you can see that n pushes cause fewer than 2n copies in total.

An everyday example

Moving to a bigger apartment

You collect records. Your shelf holds 1 record. When it is full, you buy a shelf twice as big and move every record onto it. Moving is tiring, but each move gives you as much empty space as you have records. After moving 8 records to a 16-slot shelf, you get 8 more records with no moving at all. Over time, each record has been moved fewer than 2 times on average.

How the example maps to the code
In the exampleIn the code
How many records the shelf holdsthis.capacity
How many records you ownthis.length
Buying a shelf twice as bigthis.capacity *= 2
Moving each record to the new shelfbigger[i] = this.slots[i] and this.copies++
Putting a new record in a free slotthis.slots[this.length] = value

From the slow way to amortized analysis

  1. Start with the simplest growing array: keep exactly as many slots as items. Every push makes a new array one slot bigger and copies everything across. The k-th push copies k - 1 items, so 1,000 pushes copy 0 + 1 + ... + 999 = 499,500 items. That is O(n^2) work for n pushes.
  2. The waste is copying on every push. So leave spare room: grow by 10 slots whenever the array is full. Now a copy happens only every 10 pushes. It helps, but not enough: 1,000 pushes still copy 10 + 20 + ... + 990 = 49,500 items. Each copy is still as big as the array, and copies still come at a fixed rhythm.
  3. Make the spare room grow with the array: when it is full, double this.capacity. A copy of k items now leaves k empty slots, so the next k pushes copy nothing. Big copies happen, but each one buys as many free pushes as it cost. With doubling, 1,000 pushes copy only 1,023 items.
  4. Judging this one push at a time is misleading: a single push can copy everything, yet the total over many pushes is small. So count the total work of a long sequence and divide by the number of operations. That way of counting is amortized analysis.

How it works

  1. Start with room for one item: this.capacity = 1 and this.length = 0.
  2. To push(value), first check whether the array is full: this.length === this.capacity.
  3. If it is full, double this.capacity and make a new array bigger of that size.
  4. Copy each existing item into bigger, adding 1 to this.copies for each one, then use bigger as this.slots.
  5. Write value into the next free slot and add 1 to this.length.
  6. Over n pushes, copies happen only at sizes 1, 2, 4, 8, and so on, which add up to less than 2n.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. class DynamicArray {
  2. constructor() {
  3. this.capacity = 1;
  4. this.length = 0;
  5. this.slots = new Array(1);
  6. this.copies = 0;
  7. }
  9. push(value) {
  10. if (this.length === this.capacity) {
  11. this.capacity *= 2;
  12. const bigger = new Array(this.capacity);
  13. for (let i = 0; i < this.length; i++) {
  14. bigger[i] = this.slots[i];
  15. this.copies++;
  16. }
  17. this.slots = bigger;
  18. }
  19. this.slots[this.length] = value;
  20. this.length++;
  21. }
  22. }

How fast it is

TimeO(1) amortized per push
Extra memoryO(n)

n pushes cause fewer than 2n copies in total, so each push costs a constant amount on average. The array never holds more than twice as many slots as items.

  • Best caseO(1)

    A push into an array with a free slot, like the 4th, 6th, and 7th pushes in the trace: one write, no copy.

  • Average caseO(1)

    Any long run of pushes: the total is under 3n steps for n pushes, so the amortized cost per push is constant. This is a guarantee for every sequence, not an average over lucky inputs.

  • Worst caseO(n)

    The single push that finds the array full, such as the 1,025th push, which copies 1,024 items before writing.

Common mistakes

  • Calling an operation O(1) when only its amortized cost is O(1). A single slow step can still cause a dropped animation frame.
  • Growing by a fixed number of slots. That makes the total copying O(n^2) over n pushes.
  • Shrinking by half as soon as the array is half empty. Alternating push and pop at that size then resizes on every call; shrink only when the array is a quarter full.
  • Adding up the worst case of every operation (n pushes times O(n) each) and concluding the whole run is O(n^2). Count the total work instead.

When to use it

Look for these clues in a problem:

  • An operation is usually O(1) but now and then rebuilds or copies everything.
  • Someone asks why push on an array or set on a Map counts as O(1) even though it sometimes resizes.
  • A loop inside a loop where the inner loop's total work across the whole run is limited, such as each item being pushed and popped once.
  • Designing a structure with occasional cleanups, such as a queue built from two stacks or a buffer that compacts itself.

Check yourself

Answer each one in your head first, then open it.

How many copies do 16 pushes cause, and how many do 17 cause?

16 pushes copy 1 + 2 + 4 + 8 = 15 items. The 17th push finds 16 items in 16 slots, so it copies 16 more, for 31.

Why does doubling give an O(1) average while adding 10 slots doesn't?

After doubling, the array has as many free slots as it just copied, so the copy is spread over that many cheap pushes. Adding 10 slots spreads a copy of n items over only 10 pushes.

Can a single push ever be O(n)?

Yes. A push into a full array copies every item. Amortized O(1) is about the total of many pushes, not each one.

At most how many slots can be empty after n pushes, for n of at least 2?

Fewer than n. The capacity is the smallest power of two that is at least n, which is less than 2n, so fewer than n slots are unused.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 2 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Copies happen only when the array is full, and with doubling it is full only when this.length is a power of two: 1, 2, 4, 8, and so on. So n pushes copy 1 + 2 + 4 + ... + 2^k items, where 2^k is the largest power of two below n. That sum is 2^(k+1) - 1, which is less than 2n.

Add the n writes, one per push, and n pushes cost fewer than 3n steps in total. Divide by n: under 3 steps per push, whatever the values and however long the run. That is what "O(1) amortized" means: a promise about the total of every sequence, not a guess about typical inputs.

Another way to see it is a savings account. Charge each push 3 coins: 1 pays for its own write, and 2 are saved. When the array doubles from m to 2m slots, the m / 2 items pushed since the last doubling have saved m coins, exactly enough to copy all m items. The account never goes negative, so 3 coins per push always cover the real cost.

Going deeper

3 more ideas

Why the copies stay under 2n

Copies happen only when the array is full at sizes 1, 2, 4, 8, ..., up to the largest power of two below n; call it P. Those sizes add up to 2P - 1, because each power of two is one more than all the smaller ones added together (1 + 2 + 4 = 7, one less than 8). P is less than n, so that's fewer than 2n copies: 1,000 pushes cause 1,023. So n pushes cost n writes plus fewer than 2n copies: under 3n steps, which is O(1) each on average.

Why growing by a fixed amount fails

If the array grew by 10 slots each time instead of doubling, it would copy all its items every 10 pushes. After n pushes that is about 10 + 20 + 30 + ... + n, which is about n^2 / 20 copies: O(n) per push on average. Growing by a fraction of the current size (doubling, or 1.5 times) is what keeps the average constant.

Amortized is not the same as average-case luck

An amortized bound is a promise about every long sequence, not a guess about typical inputs. Any n pushes cost under 3n steps, whatever the values. One single push can still take O(n) time, which can matter for smooth animation, so some systems grow in the background a bit at a time instead.

Work it by hand

Every step in a table, with why

Push 7 values into the doubling array and count the copies each push causes.

values pushed in order: 12, 5, 30, 8, 21, 17, 40

Stepvaluelength beforecapacity afterCopies this pushcopiesWhat happensWhy
1120100A free slot: write at index 0The array starts with room for one item, so the first push is cheap.
251211Full: double to 2, copy 1this.length === this.capacity, so it doubles and copies 12 into the bigger array before writing 5.
3302423Full: double to 4, copy 2Two items are copied, and the new array has 2 spare slots.
483403A free slot: no copyThis push is paid for by the last doubling, which left a free slot.
5214847Full: double to 8, copy 4The biggest copy so far: all 4 items move. It leaves 4 free slots.
6175807A free slot: no copyCheap again.
7406807A free slot: no copyStill cheap. The next push, the 8th, also needs no copy.

Seven pushes caused 1 + 2 + 4 = 7 copies, exactly 1 per push on average, and one slot is still free. The trace ends when the last value is written.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Amortized analysisO(1)O(n)Doubling array: you care about the total time of many pushes, which is under 3n steps, and an occasional slow push is acceptable. The O(1) is per push, amortized.
Grow by a fixed number of slotsO(n)O(n)Almost never. Each push costs O(n) on average, because copies of the whole array come every few pushes. It only makes sense if the final size is small and known.
Grow by one slot every pushO(n)O(n)Never for a growing list: every push copies everything, so n pushes cost O(n^2) in total.
Preallocate with new Array(size)O(1)O(n)You know the final size in advance. Every push is truly O(1), with no copies at all.

Extra memory: O(n): this.capacity is always less than 2n for n items, so at most about half the slots are empty. During a copy, the old and new arrays exist at the same time, briefly using about 3 times the item count.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Amortized analysis and the other approaches, on a scale where each line up is 10 times more steps.
  • Amortized analysis, Preallocate with new Array(size) O(1)
  • Grow by a fixed number of slots, Grow by one slot every push O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Amortized analysis111
Grow by a fixed number of slots101,0001 million
Grow by one slot every push101,0001 million
Preallocate with new Array(size)111

Inputs that need care

5 tricky inputs
The first push into a new array
this.capacity is 1 and this.length is 0, so the slot is free: no copy. The first copy happens on the second push.
n = 1,000 pushes
Copies happen at sizes 1, 2, 4, ..., 512, which add up to 1,023: slightly more than n, but always less than 2n. The rule is "fewer than 2n copies", not "fewer than n".
Pushing when this.length is exactly a power of two, like 1,024
That one push copies all 1,024 items. In an animation loop this can cause one slow frame, even though the average stays constant.
Adding a pop that shrinks the array to half as soon as it is half empty
At the boundary, push, pop, push, pop would grow and shrink every time, copying about n items per operation. Shrink only when the array is a quarter full, so a resize is always followed by many cheap operations.
Zero pushes
Nothing is copied and this.copies stays 0. The array still holds one empty slot from the constructor.

Variations and follow-ups

Twists interviewers add

A different growth factor

Growing by 1.5 times instead of 2 wastes fewer empty slots but copies more often. In a test with a million pushes, doubling copied about 1.05 items per push and growing by 1.5 times copied about 2.1. Both are O(1) amortized; any factor above 1 works.

Growing a little at a time

To avoid one very slow push, keep the old array while filling a new one, and copy a few old items on every push. Each push then does a bounded amount of work, so even the worst single push is O(1), at the cost of more complex code.

The potential method

A third way to prove amortized bounds: define a "potential", such as 2 * this.length - this.capacity, that rises with cheap operations and is spent by expensive ones. The amortized cost is the real cost plus the change in potential, and it comes out constant for every push.

Other structures with the same pattern

A queue built from two stacks moves each item from one stack to the other at most once, so each operation is O(1) amortized. Hash tables that double when they get too full, like the ones behind Map and Set, use the same argument as this array.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it when an operation is usually cheap but sometimes rebuilds everything, or when a loop inside a loop has an inner loop that, over the whole run, can only do so much work in total, such as each item being pushed and popped once.
  • Explain it with the total, not the worst single step: "one push can copy n items, but copies only happen at powers of two, so n pushes copy fewer than 2n items in total: O(1) amortized per push."
  • Be ready to say why doubling works and adding 10 slots doesn't: with a fixed step, a full copy comes every 10 pushes, so the total is O(n^2); with doubling, each copy is paid for by as many cheap pushes as it copied.
  • The usual follow-up is "is amortized the same as average case?". The answer is no: average case depends on the input being typical, while an amortized bound holds for every sequence of operations, even one chosen by an adversary.

Where frontend code uses it

The same idea in real UI code
  • JavaScript engines grow arrays and the hash tables behind Map and Set by a multiple of their size, which is why push and map.set count as O(1) on average.
  • Building a long string with += in a loop or with parts.push(...) then parts.join("") relies on the same kind of amortized growth inside the engine.
  • A queue built from two arrays used as stacks (common for undo buffers and task queues) moves each item between them at most once, so each operation is O(1) amortized.

Related algorithms