Micro-questions over the amortised analysis module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The lie in both directions
1. A million appends, each worst case. What does that predict, and what actually happens?
Answer
It predicts — about operations, hours of work. It takes about a tenth of a second.
2. Is the bound wrong?
Answer
No — it is useless. It assumes the worst case can happen every time, when it can only happen once per doubling, and each doubling makes the next expensive operation twice as rare.
3. Why is ” on average” also misleading here?
Answer
It invites the reader to think a probability is involved — that you might get unlucky. You cannot. The doubling structure guarantees the expensive ones are spread out. There is no unlucky input.
4. Define amortised cost.
Answer
The worst-case average cost per operation, taken over a worst-case sequence of operations. It is a guarantee, not an expectation: any sequence of appends costs at most writes in total, no matter which sequence.
B. The vocabulary
5. What is actual cost ?
Answer
What operation genuinely costs when you run it — the real number of primitive steps. For an append: 1 usually, on a resize.
6. What is amortised cost ?
Answer
A cost you assign to each operation, chosen so the assigned costs sum to at least the real costs over any sequence. An accounting fiction that happens to be a valid upper bound.
7. What is average-case cost, and what does it require?
Answer
The expected cost of one operation over a probability distribution of inputs. It requires an assumption about how likely each input is — quicksort’s assumes the pivot is not adversarially chosen.
8. How do amortised and average-case differ?
Answer
In kind, not degree. Average-case involves randomness and can be defeated by an adversarial input. Amortised involves no randomness at all and cannot be defeated, because it is a statement about every possible sequence.
9. What does amortised emphatically not mean?
Answer
That every operation is fast. It means only that over any sequence of operations, the total is .
C. The three questions
10. Lay out the three questions as a table.
Answer
| Question | Kind | Defeated by | Example |
|---|---|---|---|
| Worst single operation? | guarantee about one op | nothing | append |
| Cost on a typical input? | probabilistic expectation | adversarial input | quicksort |
| operations total ÷ ? | guarantee about a sequence | nothing | append |
11. Why is “amortised worst-case” not a contradiction?
Answer
Both the first and third rows are worst-case guarantees. They differ in what they guarantee about: one operation, or a sequence. So a structure can honestly be worst case and amortised at once.
D. The mistake this prevents
12. A hash map is average and worst case. Is it amortised?
Answer
No.
13. Why not?
Answer
Its worst case comes from collisions, which depend on the keys you insert. An adversary can pick colliding keys, and then every single lookup is — not one in a thousand, all of them. Averaging over the sequence does not help because the whole sequence is bad.
14. Why does the dynamic array get a genuine amortised bound?
Answer
Its expensive appends come from the structure’s own growth schedule, which the caller cannot influence. There is no input that makes appends collide.
15. State the test.
Answer
Ask whether the expensive operations are forced to be rare by the mechanism itself, or merely unlikely given assumptions about the input. Only the first gives an amortised bound.
E. The aggregate method
16. State the idea in one line.
Answer
Stop looking at individual operations, add up the whole sequence, and divide.
17. Derive the total copying for appends to a doubling array.
Answer
Resizes happen at sizes , and the resize at copies :
18. Say that in words.
Answer
All the resizes put together copy less than twice the number of appends, because each doubling copies as much as all previous doublings combined plus one. The last resize dominates, and it is bounded by .
19. Finish the derivation.
Answer
, so .
20. Why is the measured amortised cost not monotone in ?
Answer
It depends where falls relative to the last power of two — just after a doubling you have paid for a big copy and not yet amortised it away; just before one you have not paid yet. The bound of 3 holds throughout; the measured ratio oscillates beneath it.
21. Redo the argument for “grow by one slot”.
Answer
Every append resizes, and the -th copies :
Measured: 50,005,000 writes versus 26,383 for doubling at .
22. State the conclusion about growth.
Answer
Geometric growth is not an implementation detail — it is the entire reason the amortised bound exists. Any constant factor works; growth by a constant amount does not.
F. The accounting (banker’s) method
23. State the idea in one line.
Answer
Overcharge the cheap operations, bank the surplus, and make the expensive ones spend it.
24. Give the three rules.
Answer
- Pick an amortised cost (fee) per operation.
- Each operation pays its real cost from its fee; surplus becomes credit, shortfall must come from existing credit.
- The schedule is valid iff the credit balance never goes negative — then .
25. Work the “charge 3 per append” argument.
Answer
1 write stores the element, leaving 2 credits on it. At a resize with capacity , the array grew from to — so new elements each carry 2 credits, giving exactly credits for the copies. The balance lands on zero and never goes below.
26. Why 2 credits and not 1?
Answer
Each new element pays 1 credit to copy itself at the next resize, and 1 credit to copy an older element that has already spent its own. Every old element pairs with exactly one new one, because the array doubled.
27. Why is a fee of 2 not enough?
Answer
The bank reaches in the lab, and a proof with a negative balance is not a proof. Three is the smallest integer fee that works — which surprises people, since the copying is “about ”.
G. The potential method
28. State the idea in one line.
Answer
Instead of tracking coins on elements, define a single number measuring how much trouble the current state is storing up.
29. Give the definition of amortised cost in this method.
Answer
The actual cost plus however much the operation increased the stored-up trouble.
30. Why does the sum telescope, and what does that give?
Answer
So the amortised total bounds the actual total precisely when .
31. What is the condition on , and what do textbooks get wrong?
Answer
The potential must never end below where it started — not "". That confusion comes from textbooks assuming .
32. Give the dynamic array potential function and say what it means.
Answer
How far past the half-full mark the array has got, doubled. It is 0 immediately after a resize and climbs to equal the capacity just as the array fills — exactly what the next resize will cost.
33. Work case 1: an append with no resize.
Answer
Actual cost 1; size , capacity unchanged, so . .
34. Work case 2: an append that triggers a resize.
Answer
Size = capacity = , actual cost . , .
35. What is the signature of a well-chosen potential?
Answer
Both cases give exactly the same flat number. The expensive case’s actual cost is cancelled by the collapse in potential.
36. Give the heuristic for choosing .
Answer
should be large exactly when an expensive operation is imminent, and collapse when it happens. If it does not drop sharply on the expensive case, it will not cancel the spike.
H. The interview drill
37. State the four-step method.
Answer
- Identify which operations are expensive and how often they occur as a function of .
- Sum the expensive ones; sum the cheap ones (usually just ).
- Divide by and simplify.
- Constant → amortised. Still contains → it is not, and no averaging will fix it.
38. Cost is if is a power of 2, else 1. Derive the amortised cost.
Answer
Powers of two up to sum to ; the rest cost fewer than . So and . At : , .
39. Cost is on operation . What is the amortised cost, and what is the lesson?
Answer
, so — it grows with . The lesson: an amortised bound turns rare spikes into ; spikes that grow steadily are not rare.
I. The catalogue
40. Stack with multipop — what is the argument?
Answer
Nothing can be popped that was not first pushed. At most pushes means at most pops however they are grouped. Total , amortised . In accounting terms: charge 2 per push, and pops are free.
41. Queue from two stacks — what is the argument?
Answer
Each element moves from inbox to outbox exactly once in its lifetime — once in the outbox it is never moved back. So elements cause at most moves. The lab measures amortised exactly 1.0.
42. Binary counter increment — derive the bound.
Answer
Bit 0 flips every increment, bit 1 every second, bit every -th:
Total flips are less than twice the number of increments, because each higher bit flips half as often as the one below.
43. Why does union-find genuinely need the potential method?
Answer
Because the expensive find operations are the ones doing the work of making future finds cheap — their cost is an investment, and only a sequence-level analysis can see that.
J. When it is the wrong answer
44. Why is amortised no comfort at 60fps?
Answer
A frame has 16ms. One frame in five hundred triggering a resize drops a frame visibly. The fix is to preallocate — reserve(n) — so the resize happens once, at a moment you choose.
45. What does an amortised bound do to your p99?
Answer
Your p99 latency is precisely the expensive operations you amortised away. A structure with worst-case can beat one with amortised on p99 while losing on throughput.
46. Does the amortised bound apply to a single operation in isolation?
Answer
No. Amortisation is a statement about sequences; with one operation there is no sequence.
47. Give the honest summary.
Answer
Amortised is the right answer for throughput and the wrong answer for latency.
K. Traps
48. Is quicksort amortised ?
Answer
No — it is average-case and is not amortised anything. Running it a thousand times does not make a sorted-input run cheaper.
49. What is the shrink-at-half trap?
Answer
Add a pop that shrinks as soon as size falls to half the capacity, and an adversary can sit exactly on the boundary, forcing a resize every operation — per operation forever. The fix is to shrink only at one quarter full, leaving a hysteresis gap.
50. Why can your argument never read the credit balance at runtime?
Answer
Credit is fictional. There is no field in the struct holding credits — it is a bookkeeping device for proving the total stays bounded.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
- Amortized Analysis — the module
- Growth & Asymptotics — Question Bank
- Dynamic Arrays — Question Bank — the running example
- Union-Find — Question Bank — the case needing the potential method
Software engineering
Infrastructure & security
Computer science
Hardware & engineering