Unit 1.2 · about 4 h
89 / 324Aggregate, accounting and potential amortized analysis
Appends, queue transfers and table resizes all hide rare expensive steps inside cheap sequences. Without amortization you either over-reject a fine structure or ship a latency spike.
- derive
You can now
- Distinguish worst-case-per-operation from amortized cost over a sequence, and name which one a latency-critical loop needs.
- Derive the \(b/(b-1)\) per-push bound for geometric growth from the series, and compute copy totals for \(b = 2\) and \(b = 1.125\).
- Prove binary-counter and dynamic-array bounds by the summation, taxation and potential methods, including the \(\Phi = 2\mathrm{num} - \mathrm{capacity}\) derivation.
Covers
- Aggregate, accounting and amortized reasoning
- Potential-function amortized proofs
Study, in this order
3 steps
- Amortised analysis (inside Computational complexity and Big-O)DSA Handbook - Foundations and linear patterns
Amortised analysis: the aggregate, banker and potential methods on the dynamic-array example, plus the hard-real-time caveat
Depth · Read only this section; the rest of the chapter belongs to the previous unit.
- Dynamic array internalsDSA Handbook - Foundations and linear patterns
The proof in one paragraph (geometric series to \(b/(b-1)\)); How fast capacity actually grows (the 1000-push copy counts for \(b = 2\) and \(b = 1.125\)); Five libraries (the CPython 1.125 row with the
listobject.cformula and the python-dev history); What happens on the way down (shrink hysteresis); the Python-doubles and front-insertion warnings - Lecture 9: Amortized Analysis, Sections 9.1 to 9.3Algorithms lecture notes - amortized analysis and hashing
9.1 Incrementing a Binary Counter; 9.2 Counting from 0 to \(n\) with 9.2.1 Summation, 9.2.2 Taxation, 9.2.3 Charging and 9.2.4 Potential (amortized cost 2 per increment); 9.3 Incrementing and Decrementing (the double-binary counter); 9.5 Generalities and Warnings
Depth · Skip 9.4 Gray Codes; it is depth material for later. 9.5 is one page on why one structure can have several valid sets of amortized bounds.
Focus on
- Every method answers one question: total cost of the sequence divided by its length. Summation counts flips, taxation banks credit, potential tracks \(\Phi\).
- The proof needs geometric growth: with factor \(b\) the copies sum to at most \(n/(b-1)\); arithmetic growth collapses to \(\Theta(n)\) per push.
- CPython grows lists by about 1.125x after the small-list steps 0, 4, 8, 16: about nine moves per push, the highest constant in the table, chosen to bound peak RAM.
- Shrinking needs hysteresis (shrink at a quarter full, not a half) or alternating push and pop replays the resize forever.
Reproduce closed-book
sys.getsizeof that capacity steps land at lengths 1, 5, 9, 17, 25 and 33.Traps
- Amortized \(O(1)\) does not bound the single slowest push; the resize push copies everything.
- Python lists do not double. The formula is
(newsize + (newsize >> 3) + 6) & ~3after the 0, 4, 8 start. - Halving on pop breaks the bound; only the quarter rule (or no shrinking) keeps it.
Practice
LeetCode 232: Implement Queue using Stacks
Implement the two-stack lazy transfer. In your solution note, prove each element moves at most twice, so the amortized cost per operation is \(O(1)\). Judge with the Example sequence push 1, push 2, peek, pop, empty.
After submitting, read the handbook queues-deques section Why the patterns chapters teach the rest for the lazy-transfer argument.
Self-test
-
Derive the amortized cost per push for growth factor 2.
Resizes copy \(1 + 2 + 4 + \cdots + n/2 = n - 1\) elements; plus \(n\) slot writes the sequence costs \(2n - 1\), so at most 2 per push. The potential method with \(\Phi = 2\mathrm{num} - \mathrm{capacity}\) gives the looser constant 3; both are \(O(1)\). -
In the potential proof, why is the resize push amortized 3 and not \(k+1\)?
Actual cost \(k+1\) plus the \(\Phi\) change. Before the push the table is full so \(\Phi = 2k - k = k\); after, \(\mathrm{num} = k+1\) and \(\mathrm{cap} = 2k\) so \(\Phi = 2\). The change is \(2-k\) and the amortized cost is \((k+1) + (2-k) = 3\). -
How many bit flips do \(n\) binary-counter increments from zero perform, exactly?
\(2n\) minus the number of 1 bits in \(n\). Bit \(i\) flips every \(2^i\) iterations, so it flips \(\operatorname{floor}(n/2^i)\) times. -
Push then pop alternately at the half-full boundary with a halving shrink policy. What breaks?
Every operation triggers a full resize, so \(n\) operations cost \(\Theta(n^2)\). Shrink only at a quarter full.
Completion criterion
Stop when
You derive the resize-push bound from \(\Phi\) without notes, and your queue solution states its amortized argument next to the transfer code.
Mark passed, then open 1.3 Only mark this when you can do it without notes.Leads to
- 1.5 Hash tables: collisions, load factor, resizing and tombstones Table resizing reuses the same doubling proof with the load factor as the trigger.
- 1.6 Stacks, queues, deques and monotone structures The two-stack queue is the next amortized argument.
Comes after
- 1.1 Cost models, asymptotic notation and casesAmortized bounds reuse the same definitions with the average taken over a sequence.
Resources for this unit
- DSA Handbook - Foundations and linear patterns Study Part 0, Part 1, Part 3 and Part 4 in order, plus the Part 5 Linked-list fundamentals chapter. Use the routing-rule pages for arrays versus lists, map choice, stack versus queue, two pointers, sliding windows and prefix methods before seeing solved code.
- Algorithms lecture notes - amortized analysis and hashing Use note 9 Amortized Analysis for the summation, taxation, charging and potential-function proofs, and note 5 Hashing for chaining, universal hashing and open-addressing analysis, when the handbook treatment is too brief for a proof.
Also in this section
- AlgoMaster DSA - linear structures slice Attempt Design HashMap, Longest Substring Without Repeating Characters and Sliding Window Maximum cold. Hide tags, state the invariant first, and add randomized operation histories to Design HashMap.
- MIT 6.042J - asymptotics and invariants Use the asymptotics, state-machine invariants and proof-method readings when a cost or correctness argument is weak. Solve only the matching problems.
- Algorithmica - memory and data layout Read the memory hierarchy, cache and complexity-model chapters, then measure one contiguous-versus-linked and one hash-versus-ordered workload crossover.
- NeetCode - unseen linear problems Use only for two tag-hidden transfer problems after the AlgoMaster slice. Do not start another full roadmap or watch a solution before the attempt is complete.
- Hypothesis documentation - Quickstart and stateful testing Follow Quickstart for
@givenstrategies and the pytest combination, Configuring test settings formax_examplesandderandomize, then Rule-based state machines (rule,precondition,invariant,run_state_machine_as_test) for randomized operation histories againstdictanddequeoracles. - CPython source - list and dict objects Read
list_resizeinObjects/listobject.cfor the growth formula and pattern comment, and theUSABLE_FRACTIONdefinition, perturbation-probing comment and dummy-entry handling inObjects/dictobject.c. Read the cited functions and comments only.