Suppose we start empty and pushn items. We double capacity each time the array is full. Capacities reached: 1,2,4,8,…
Step 1 — cheap inserts. Each of the n pushes costs 1 to write the element.
cheap cost=nWhy this step? Every element must be written exactly once into its slot.
Step 2 — copy costs at resizes. A resize at capacity 2k copies 2k old elements. Resizes happen at sizes 1,2,4,…,2m where 2m≤n.
copy cost=1+2+4+⋯+2m=∑i=0m2i=2m+1−1Why this step? Geometric series — each doubling copies the whole current array once.
Step 3 — bound the sum. Since 2m≤n, we have 2m+1−1<2n.
copy cost<2n
Step 4 — total and divide.Total=n+2n=3n=O(n)Amortized cost per push=n3n=3=O(1)
Why this works: the copies form a geometric series that sums to a constant multiple of n, not n2. The rare doublings are "paid for" by the many cheap inserts before them.
Total cost of n operations is O(n), so cost per operation averaged over the sequence is O(1) — a worst-case guarantee over a sequence, not per single op.
Why is doubling array capacity amortized O(1) per insert?
Copy costs form a geometric series 1+2+4+…+2^m < 2n, plus n writes → total 3n = O(n), so 3 per op.
What is the total copy cost when growing by +1 each time, and the amortized cost?
Difference between amortized and average-case complexity?
Amortized = deterministic worst-case over a sequence; average-case = expectation over a probability distribution of inputs.
State the potential function used for dynamic array doubling.
Φ = 2·size − capacity (≥0 when ≥ half full).
In the accounting method, how much is each push charged and why?
3 units: 1 for the write, 2 saved as credit to pay for future copies of itself and a neighbor.
Why might amortized O(1) be unacceptable in real-time systems?
A single resize is O(n) — a latency spike — even though the average is constant.
What growth factor requirement guarantees amortized O(1) inserts?
Multiplicative (geometric) growth by any factor > 1; additive growth fails.
Recall Feynman: explain to a 12-year-old
Imagine filling a small box with toys. When it's full, you buy a box twice as big and move all toys over — that move is slow. But because each new box is double the last, you only move toys a few times even after hundreds of toys. So most of the time adding a toy is super fast, and the rare slow moves are tiny when you spread them out. On average, adding a toy is fast — that's "amortized O(1)."
Dekho, amortized O(1) ka simple matlab hai: kabhi-kabhi ek operation mehnga (slow) hota hai, lekin agar woh bahut rarely hota hai, toh poore sequence pe average cost constant reh jaati hai. Jaise dynamic array (Python list, vector) mein jab array full ho jaaye toh usko bada karke saare elements copy karne padte hain — yeh O(n) ka kaam hai. Lekin trick yeh hai ki hum capacity ko double karte hain, +1 nahi.
Kyun double karna zaroori hai? Maan lo har baar +1 se badhao, toh copies ka total 1+2+3+...+n = n²/2 ho jaata hai — yeh O(n²) hai, har insert effectively O(n)! Par doubling se copies banti hain 1+2+4+8+... jo geometric series hai aur yeh 2n se kam rehti hai. Toh total kaam = n writes + 2n copies = 3n = O(n). Isko n se divide karo toh per operation sirf 3 units = O(1). Yahi magic hai geometric series ka.
Ek important baat — amortized O(1) ka matlab yeh nahi ki har operation fast hai. Resize wala ek single push toh genuinely slow (O(n)) hota hai, ek spike aata hai. Bas average constant hai. Aur isko average-case mat samajhna — average-case mein probability hoti hai, jabki amortized ek guaranteed worst-case hai poore sequence ke liye, chahe input kaisa bhi ho.
Hash table mein bhi yahi funda lagta hai: jab load factor (size/capacity) threshold cross kare, toh rehash karke table double kar dete hain. Same geometric argument se insert amortized O(1) ban jaata hai. Bas yaad rakho: "Double karo, add mat karo — mehnga cost spread ho jaata hai."
