Accounting (Banker's) Method & Potential Functions

The aggregate method assigns every operation the same amortized cost. The accounting method (also called the banker's method) is more flexible: it lets us assign different amortized charges to different operations, as long as we never go broke.

Accounting method. Assign each operation an amortized cost (a fixed "fee" we charge it). When an operation's fee is more than its real cost, the surplus is stored as credit on the data structure. When an operation's fee is less than its real cost, it pays the difference using stored credit.

The one rule: the total credit must never become negative — you can only spend what you've already banked. If that holds, the total amortized cost is a valid upper bound on the total real cost.

The intuition is prepayment: cheap operations are overcharged on purpose, and the extra money sits in the "bank" to cover a future expensive operation. It's like paying a little extra into savings each month so a big annual bill is already funded when it arrives.

Why do we deliberately overcharge some cheap operations? Because the rare expensive operation cannot afford itself. By the time a resize (or split, or rehash) happens, it needs to pay an O(n) bill in a single step. If we charged it its true cost, its amortized cost would be O(n) — useless.

Instead, we pre-collect that money from the many cheap operations leading up to it. Each cheap append is charged a little extra; that surplus becomes credit attached to the elements. When the expensive resize finally fires, the credit is already sitting there to pay for copying — so the resize itself is charged nothing extra, and its amortized cost is O(1).

The credit is an accounting fiction — no real memory or time is stored. It is purely a bookkeeping device to prove that the average cost is low. The requirement "credit ≥ 0 at all times" is what makes the proof valid: it guarantees the prepayments always arrive before the bill.

Charge every append an amortized cost of 3 (a constant → O(1)). Watch the credit stay non-negative.

Each append's real work is either 1 (just store, no resize) or 1 + copies (store + copy everything on a full array). We claim charging $3 per append always covers it:

Why $3 suffices: when the array doubles from n/2 to n, exactly the n/2 newest elements (added since the last resize) each carry $2 of banked credit. The resize must copy all n/2 old elements — but each of those was among the "new" ones last round and banked $1 for exactly this copy. The credit is always there:

Since the bank never goes negative, $3 per append is a valid upper bound → amortized O(1) per append. Same conclusion as the aggregate method, reached by a different, more flexible argument.

The potential method is the most general technique. Instead of attaching credit to individual elements, it defines a single potential function Φ (phi) that maps the entire state of the data structure to a number — think of it as stored energy or "how messy / how full" the structure currently is.

Potential method. Define Φ(Dᵢ) = potential of the data structure after the i-th operation, with Φ(D₀) = 0 and Φ(Dᵢ) ≥ 0 always. The amortized cost of an operation is its real cost plus the change in potential it causes:

Example

Copy

amortized_cost = real_cost + ( Φ(after) − Φ(before) )

• A cheap operation that raises potential (fills the structure) pays a little extra — the surplus is stored as increased Φ.
• An expensive operation that lowers potential (a resize empties the "fullness") is refunded from the drop in Φ, so its amortized cost stays small.

Because the potential telescopes, the total amortized cost = total real cost + Φ(end) − Φ(start) ≥ total real cost (as long as Φ starts at 0 and stays ≥ 0). So summed amortized cost is always a valid upper bound. The whole art is choosing a good Φ.

For a dynamic array, pick a potential that is zero right after a resize (when the array is exactly half full) and grows as it fills toward the next resize:

Check the requirements:

• Just after a resize, size = capacity/2, so Φ = 2·(cap/2) − cap = 0 ✓ (and it's the minimum, so Φ ≥ 0).
• Just before a resize, size = capacity, so Φ = 2·cap − cap = cap — a full reservoir of stored energy.

Now the two cases:

The huge O(n) copy cost is exactly cancelled by the O(n) drop in potential that the resize releases. Both cases give amortized O(1) — a third independent proof of the same result. The potential Φ = 2·size − capacity was "storing" precisely enough energy to fund the next copy.

All three prove the same amortized bounds; they differ in style and convenience:

Rule of thumb: the aggregate method is the quickest when a total is easy to sum; the accounting method gives the clearest intuition; the potential method is the most powerful and generalizes to complex structures.

For the dynamic array, all three techniques agree:

The methods are interchangeable proof tools — pick whichever makes a given problem cleanest.