Skip to main content

Potential Method and Formal Amortized Cost Accounting

What This Concept Is​

For state potential Phi, define amortized cost as actual cost plus the change in potential. Telescoping gives `sum actual = sum amortized + Phi(initial)

  • Phi(final)`. If final potential is nonnegative, the initial potential is an explicit additive budget. It need not be zero if that cost is accounted for.

Why It Matters Here​

The equality is the proof mechanism. It reveals why dropping initial potential or selecting the wrong coefficient can make a constant amortized claim false under the stated primitive costs.

Concrete Examples​

Doubling array. Start size=capacity=0, and use Phi=2*size-capacity on the reachable append-only states. Potential stays nonnegative: after growth the array is at least half full. A non-resizing append costs 1 and increases Phi by 2, so amortized cost is 3. A resize from full capacity c to 2c costs c+1 and changes Phi from c to 2, so amortized cost is also 3. The first allocation from 0 to 1 has actual 1 and potential change 1, cost 2. This proves the bound at every prefix under the lab's copy/write model.

Queue coefficient. With push/pop unit primitives, choose Phi=2*len(In). Enqueue has amortized 1+2=3. A dequeue transferring k elements has actual 2k+1 and potential change -2k, leaving amortized 1. Phi=len(In) leaves k+1 unpaid and does not establish a constant per-operation bound in this model.

Limits. Phi=0 yields amortized cost equal to actual cost; it does not magically convert an aggregate proof into uniformly cheap operations. Nonnegative potentials cannot be assumed for unreachable or newly allowed states; adding deletions to the array makes a fresh derivation necessary.

Common Confusion / Misconceptions​

Potential is not required to increase on every cheap operation or decrease on every expensive one; the needed inequalities are what matter. No theorem says Fibonacci or splay heaps cannot be described with a credit account. Avoid calling the method a substitute for specifying costs.

How To Use It​

Write the telescoping identity first. Prove the required potential lower bound on reachable states, include initial credit and compute every operation case. Save a table of actual cost, before/after potential and amortized charge, then verify the sum numerically on a small trace and algebraically in general.

Check Yourself​

When may initial potential be nonzero? Why is the queue coefficient 2 here? Why can an append-only potential fail after deletion?

Mini Drill or Application​

For sizes 0 through 3 in the array model, capacities are 0,1,2,4. Feedback: potentials 0,1,2,2; actual costs 1,2,3; amortized costs 2,3,3. Verify telescoping total actual 6.

Read This Only If Stuck​

CLRS: potential method and dynamic-table cases. Compare the exact primitive cost scale with the lab evidence table.