Complexity and amortization
Why you care
Most "it was fast in testing" incidents in ETL are cost-model mistakes: a job that was instant on 40,000 rows crawls on 400,000 because one linear line sat inside a loop. On the job you must say which claim a number makes: worst case, expected, or amortized. Interviewers ask about amortization because it separates a per-call guarantee from a per-run one.
Explain like I'm 5
A bus conductor collects fares. Most stops cost a nod. Occasionally the bus is full and everyone changes to a bigger bus, and that stop is slow. The cost per stop over the route is small, because bigger buses are bought rarely. That average is the amortized cost, not a promise about one stop.
Core concept
Three questions hide behind "complexity":
- Worst case: maximum work over all inputs of size n; holds for every call.
- Expected case: average over a stated input distribution or the algorithm's random choices. Hash lookup is O(1) on average if keys spread out; the CPython docs say that if every key hashes to the same value each operation takes O(n). That is average-case, not amortization.
- Amortized case: the worst-case total of m operations divided by m. No probability, any sequence, silent about one call.
Big-O is an upper bound (n steps is also O(n²)); Theta is the tight bound. Mean Theta when you quote a cost.
Prove amortized bounds by aggregate counting, which means totalling the work: with doubling, copies happen at sizes 1, 2, 4, and so on, so n appends copy under 2n items. Or by charging: each item pays a fixed fee when pushed that covers its one later move or pop.
Decision rule: use worst case when one call has a deadline, expected when you can defend the input distribution, amortized when only the run total matters.
Minimal example Counting copies in a doubling array
cap, size, copies = 1, 0, 0
for _ in range(1000):
if size == cap:
copies += size
cap *= 2
size += 1
print(size, cap, copies)
print(copies < 2 * size, copies / size)1000 1024 1023
True 1.023In production Each pushed item is popped at most once
A nested while looks quadratic. Charging shows it is not: each reading is pushed once and popped at most once. The block prints the worst single step and the total.
def track(readings):
stack, pushes, pops, worst_step = [], 0, 0, 0
for r in readings:
step = 0
while stack and stack[-1] <= r:
stack.pop()
pops += 1
step += 1
stack.append(r)
pushes += 1
worst_step = max(worst_step, step)
return stack, pushes, pops, worst_step
readings = [9, 8, 7, 6, 5, 4, 3, 2, 1, 10, 3, 2, 12]
stack, pushes, pops, worst = track(readings)
n = len(readings)
print("n", n, "pushes", pushes, "pops", pops)
print("worst single step", worst, "of", n)
print("pops <= pushes:", pops <= pushes)
print("left on stack", stack)
for size in (1_000, 10_000):
data = list(range(size, 0, -1)) + [size + 1]
_, pu, po, wo = track(data)
print(size, "worst step", wo, "total pops", po, "pops/n", round(po / len(data), 3))n 13 pushes 13 pops 12
worst single step 9 of 13
pops <= pushes: True
left on stack [12]
1000 worst step 1000 total pops 1000 pops/n 0.999
10000 worst step 10000 total pops 10000 pops/n 1.0See it happen A full array pays once, then goes quiet
- Three appends fill slots 0 to 2 and each costs one write.
- The fourth append fills the last slot; the array is exactly full.
- The fifth append finds no room, so a larger array is allocated and nothing is copied yet.
- All four existing items are copied across: this one append costs about n.
- The new item is written and the old array is released.
- Three more appends cost one write each, which pays for the earlier copy.
In your world
The situation
Your reconciliation job drains unmatched settlement ids with queue.pop(0) in a Jenkins stage with a 30-minute timeout. At 40,000 ids it takes seconds.
What actually breaks
At 400,000 ids the stage slows about 100× and eventually misses its window, and your code raised nothing. Each pop(0) shifts every remaining element: about n²/2 moves, 8×10¹⁰ versus 8×10⁸.
What you'd do on Monday
Use a structure with O(1) front removal. The amortized claim for end append and pop() does not cover pop(0).
from collections import deque
pending = deque(unmatched_ids) # O(n) once
while pending:
sid = pending.popleft() # O(1), no shifting
reconcile(sid)Imagine you work at Netflix
The numbers
Illustrative: a consumer appends 50,000 playback events/s to a list flushed each minute: 50,000 × 60 = 3,000,000 appends, a 24 MB array at 8 B per slot. At growth factor 1.125, total copying is about n/(g-1) = 3,000,000 / 0.125 = 24,000,000 moves, 8 per append. The last resize alone moves about 2.6M slots, roughly 21 MB, in one call.
What the Scenario-A answer does here
The Scenario A fix still holds, but "append is O(1)" is not a latency budget. One append copies 21 MB and stalls the consumer while events keep arriving.
What flips at this scale
The question changes from the average to the worst single call. The consumer uses a fixed-capacity buffer (deque(maxlen=...) or a pre-sized list) flushed on count or time, so no hot-path call is linear.
The trade-off you'd defend
I would defend a fixed-capacity buffer over an unbounded list, trading simplicity and unbounded growth for a bounded worst-case call and a memory ceiling I can alert on.
Illustrative figures chosen to make the arithmetic visible; not Netflix-published numbers.
Gotchas
Amortized append quoted as a latency bound
p99 of a handler that appends to a growing list spikes periodically while the mean is flat.
append is O(1) amortized; the call that triggers a resize copies the whole list.
Preallocate, cap the buffer, or flush at a fixed size.
Hash average mistaken for a guarantee
A service keyed on user-supplied strings crawls on a crafted batch.
O(1) lookup assumes keys spread out; heavy collisions make each operation O(n).
State the assumption; cap input size.
Tricky questions
Yes, both mean usually fast and occasionally slow.
No. Average needs a probability assumption about inputs. Amortized is a worst-case total over any sequence divided by its length.
Scenario question
A teammate says "append is O(1), so latency is fine", but p99 spikes every few seconds. How do you respond?
Model answer
I'd say they are quoting an amortized bound as a worst-case one, and I'd confirm by logging list length on slow calls. If the spike matters, I'd use a fixed-capacity buffer flushed by size, accepting a drop-or-block policy when it fills. The trade-off is simplicity against a bounded worst-case call.
Interview corner
CommonWhat is amortized analysis?
TrickIs hash-table lookup O(1) amortized?
CommonWhat is the difference between Big-O and Theta?
Memory hook
A bus conductor's average fare time is tiny, but the stop where everyone changes buses takes as long as the whole bus.
Amortized is a promise about the total over a run, never about one call.
Self-check
What separates amortized from average-case cost?
Amortized is a worst-case total over any sequence divided by its length; average-case needs a probability assumption.
Why is doubling-array append O(1) amortized?
Copies happen at sizes 1, 2, 4, and so on, so n appends copy under 2n items.
Why is a
whileinside afornot automatically O(n²)?If each item is pushed and popped at most once, inner runs total at most n.
Extend the doubling simulation to track the largest single-append copy. Run n = 1,000, 100,000 and 1,000,000 and paste three lines of n, total copies, copies/n, largest copy. Success means copies/n stays under 2 while the largest copy grows with n.