Learn the vocabulary of averaging an occasional expensive operation across a long sequence of cheap ones.
0 / 5 completed
1 / 5
At standup, a dev mentions a dynamic array whose individual append is occasionally slow because it triggers a full resize, but averaged out over a long sequence of appends, each one still costs constant time overall. What is this kind of cost analysis called?
Amortized complexity is exactly this: an occasional expensive operation, like a full resize on append, is spread mathematically across the whole sequence of operations, so even though any individual append can occasionally be slow, the average cost per append over a long run still works out to constant time. A hash collision is an unrelated hash-table concept about two keys sharing a bucket, not about averaging cost over a sequence. This amortized view is exactly why a dynamic array's append is still described as constant time overall, despite the occasional expensive resize.
2 / 5
During a design review, the team picks a dynamic array's growth strategy to double its capacity each time it resizes, rather than growing by a small fixed amount. Which capability does doubling provide for the amortized cost of append?
Doubling the capacity keeps append's amortized cost constant, since resizes become exponentially rarer as the array grows larger, and the total cost of all the resizing work done across a long sequence of appends still only adds up to a constant amount per append when averaged out. Growing by a small fixed amount instead makes resizes happen far more often relative to the array's current size, pushing the amortized cost of append toward linear rather than constant. This doubling strategy is exactly why a well-implemented dynamic array's append stays cheap on average no matter how large it eventually grows.
3 / 5
In a code review, a dev notices a dynamic array's growth strategy adds a small fixed number of extra slots on every resize instead of doubling its capacity, meaning it has to resize far more often as the array grows large. What does this represent?
This is a dynamic array whose amortized append cost degrades toward linear, since growing by a small fixed amount each time means the number of resizes needed to reach a given size grows proportionally with that size, rather than staying logarithmic the way doubling keeps it. A cache eviction policy is an unrelated concept about discarded cache entries. This fixed-growth pattern is exactly the kind of subtle performance regression an amortized-complexity-aware reviewer would flag, since it looks correct but scales far worse than a doubling strategy as the array grows large.
4 / 5
An incident report shows a service building up a large in-memory list saw append performance degrade sharply as the list grew, because the underlying dynamic array's growth strategy added only a small fixed number of slots per resize instead of doubling, forcing far more frequent resizes at large sizes. What practice would prevent this?
Switching the dynamic array's growth strategy to double its capacity on each resize keeps resizes exponentially rarer as the list grows, restoring append's amortized cost back to constant regardless of how large the list eventually becomes, which is exactly the fix for the degradation described in this incident. Continuing to grow by a small fixed number of slots per resize is exactly what forced far more frequent resizes and the sharp performance drop at large sizes. This doubling strategy is the standard, well-understood fix for a dynamic array whose growth policy was undersized for its actual workload.
5 / 5
During a PR review, a teammate asks why the team is comfortable calling a dynamic array's append "constant time" given that some individual appends are visibly much slower than others because of an occasional resize. What is the reasoning?
Amortized analysis looks at the total cost of a long sequence of operations rather than judging any single operation in isolation, and with a doubling growth strategy that total cost across a sequence of appends stays proportional to the number of appends, even though any one individual append can occasionally be far more expensive than the rest because of a resize. This is why "amortized constant time" is a precise, meaningful claim about the average cost per operation over a sequence, not a claim that every single operation costs exactly the same. The tradeoff is that amortized guarantees say nothing about the worst case of any single operation, which matters for a caller with a hard real-time latency requirement on every individual call.