← ~/visualizations

amortized-analysis

Visualizes amortized cost via the potential method using a dynamic array push sequence. Actual costs (including occasional resize-copy spikes) are shown alongside constant-ish amortized costs, while a potential “credit tank” Phi(S) stores and releases credit so that a_i = c_i + Phi(S_i) − Phi(S_{i−1}). The bottom panel shows the telescoping sum Σa_i = Σc_i + Phi(S_n) − Phi(S_0), illustrating how nonnegative potential bounds total actual work over the whole sequence.

canvasclick to interact
t=0s

practical uses

  • 01.Proving O(1) amortized push in dynamic arrays (vector/ArrayList growth)
  • 02.Analyzing amortized bounds in stacks/queues (e.g., multipop, two-stack queue)
  • 03.Reasoning about splay trees, union-find, and other data structures with occasional expensive operations

technical notes

Time-driven 3.6s operation cycles; persistent closure state simulates a sequence of pushes with doubling resizes. Bars plot recent actual vs amortized costs; a blocky token animation illustrates paying c_i and storing/spending ΔPhi. Uses snap-to-grid sizing for a retro aesthetic and ease() for smooth transitions.