Intuition The one core ideaA dynamic array or hash table sometimes does a slow "grow the box" step, but if you double the box each time, those slow steps are so rare that the average work per operation stays constant. This whole topic is just the arithmetic that proves "occasionally slow + rare enough = constant on average."
Before you can read the parent note 3.3.7 Amortized O(1) , you need to earn every symbol it throws at you. Below, each idea is built from nothing, shown as a picture, and justified by the question it answers. Read top to bottom — each block uses only what came before it.
Definition Cost of an operationA cost is simply how many basic steps an operation takes — one "step" = writing one number into one slot, or copying one number from an old box to a new box.
We do not measure seconds; we count steps , because steps don't change when you buy a faster computer.
Think of a row of little boxes (slots). Writing a toy into one box = 1 step . Moving a toy from an old row to a new row = 1 step . That's all "cost" ever means here.
Why the topic needs it. Everything later ("O ( n ) adding up these steps . If you can't count steps, none of the sums make sense.
Definition size and capacity
capacity = how many slots the box has (empty or full).size = how many slots are currently filled .
A box is full when size = capacity
Imagine an egg carton. capacity = number of egg-holes in the carton. size = number of eggs actually sitting in it. When every hole has an egg (size = capacity), you can't add another egg without a bigger carton.
Why the topic needs it. A resize is triggered exactly when size would exceed capacity. Every formula in the parent — the potential Φ = 2 ⋅ size − capacity
Definition push and resize
A push adds one new item into the next empty slot. Normal cost: 1 step .
A resize happens when the box is full: allocate a bigger box, copy every existing item over, then push the new one. Cost: (number of items copied) + 1.
Pushing = dropping one egg into an empty hole (fast). Resizing = the carton is full, so you buy a new, bigger carton, move every egg across one at a time , then add the new egg (slow).
Why the topic needs it. The entire question of the topic is: resizes are slow — how slow are they on average? You must know a resize copies all current items before you can count that cost.
2 k k k exponent — it counts how many times we doubled .
2 0 = 1 , 2 1 = 2 , 2 2 = 4 , 2 3 = 8 , …
Intuition Why this notation?When we double the box each time, the capacities we pass through are 1 , 2 , 4 , 8 , … 2 k k k m index — a counter, not a real quantity.
Why the topic needs it. The parent writes "resizes happen at sizes 1 , 2 , 4 , … , 2 m
∑ 1 + 2 + 4 + …
Why the topic needs it. The total copy cost of all resizes is written as one ∑
Intuition The picture that makes it obviousStack blocks of width 1 , 2 , 4 , 8 as wide as everything before it plus one . So the whole stack never grows past twice the last block . That is the heart of the whole topic: all the past copying together is less than twice the most recent copy.
Why the topic needs it — and why THIS tool. We use a geometric series (each term multiplied by a fixed factor 2) instead of an arithmetic series (each term plus a fixed amount) because geometric sums stay linear (< 2 n quadratic (n 2 /2 O ( 1 ) O ( n ) Geometric Series .
==n
==O ( f ( n )) how the cost grows as n , ignoring constant multipliers.
O ( 1 ) doesn't grow with n O ( n ) in proportion to n O ( n 2 ) n squared (quadratic — very bad).
Plot cost against n O ( 1 ) O ( n ) O ( n 2 ) which shape? — not the exact height.
Why the topic needs it. The punchline "amortized O ( 1 ) O ( n 2 ) Big-O Notation .
Load factor α = capacity size α = 0.5 α hash table does a rehash (its version of a resize).
Same egg carton, but now expressed as a percentage full . α = 0.5 hash table deliberately keeps itself not too full so lookups stay fast — see Load Factor .
Why the topic needs it. Example 2 in the parent triggers resizing off α
Definition Amortized costThe amortized cost of one operation = (total cost of n ÷ n fair share each operation owes, even if some ops secretly did more work.
Φ Φ savings account of pre-paid work . Cheap operations deposit into it; the expensive resize withdraws from it. Defined so it never goes negative.
amortized cost = actual cost + ΔΦ ΔΦ change in the account, (after) − (before).
Every cheap push puts a couple of coins in a jar sitting next to the array. When a resize demands lots of work, you smash the jar and the saved coins pay for it — so the resize looks cheap in the averaged books. See Potential Method and Stack with Multipop for another example of the same trick.
Why the topic needs it. The parent's formal proof uses Φ = 2 ⋅ size − capacity Φ ΔΦ
Geometric series stays linear
Amortized cost = total over n
Potential Phi savings jar
Test yourself — cover the right side.
I can say what a "cost" of 1 step physically means One write of a number into a slot, or one copy of a number to a new box; we count steps, not seconds.
I can define size vs capacity capacity = total slots the box has; size = slots currently filled; full means size = capacity.
I know what a push costs normally and during a resize Normal push = 1 step; resize = copy all current items + 1 write.
I can read 2 k 2 0 = 1 , 2 1 = 2 , 2 2 = 4 , 2 3 = 8
I can expand ∑ i = 0 m 2 i 2 0 + 2 1 + ⋯ + 2 m 2 i
I know the geometric-series shortcut 1 + 2 + 4 + ⋯ + 2 m = 2 m + 1 − 1
I can tell O ( 1 ) O ( n ) O ( n 2 ) Flat line, straight slope, upward-bending curve — respectively.
I can compute load factor from size and capacity α = size / capacity
I know what amortized cost is Total cost of n operations divided by n — the fair share each op owes.
I know what Φ ΔΦ Φ ΔΦ
Amortized O(1) operations — the parent topic these foundations unlock.Dynamic Arrays — where size/capacity/resize live.Hash Tables — same resize math via rehashing.Load Factor — the α Geometric Series — the 1 + 2 + 4 + ⋯ < 2 n Big-O Notation — the growth shapes.Potential Method — the Φ Stack with Multipop — another amortized example using the same jar idea. 
