Amortized Analysis

stored credit

When the accounting method overcharges a cheap operation, the extra payment has to live somewhere until it is needed. Stored credit is that saved-up money, conceptually parked on specific pieces of the data structure — individual array slots, stack items, counter bits, tree nodes. It is not real memory or a real variable in the program; it is a bookkeeping fiction the analyst uses to track which future expensive work has already been prepaid.

Placement is what makes credit useful. You attach credit to exactly the elements that will later be expensive to handle, so that when the expensive operation arrives, the credit needed is sitting right where the work happens. For a binary counter under the accounting method, you keep the invariant 'every bit that is currently 1 carries 1 unit of stored credit.' Setting a 0 to 1 costs you 2 (1 to flip it, 1 to put as credit on that new 1-bit); clearing a 1 to 0 during a carry is then free because the bit's own stored credit pays for the flip. The credit is literally located on the 1-bits, which are exactly the bits that future carries will have to clear.

Stored credit is the concrete object the accounting method manipulates, and the non-negativity rule is really 'no element ever owes credit it does not have.' The deep point is that stored credit is the same quantity that the potential method packages as a single number: the potential function is just the total credit summed over all elements. Choosing where to store credit (accounting) and choosing a potential function (physicist's method) are two views of one idea. The caveat: credit is a proof device, not a runtime cost — it changes nothing the program does, only how you account for the work.

Binary counter invariant: each 1-bit holds 1 credit. Increment 0111 to 1000: three 1-bits clear to 0 (each flip paid by its own credit, free) and bit 3 sets to 1 (cost 2: flip plus new credit). The increment's amortized cost is 2, independent of how many carries cascade, because the cascading clears were all prepaid.

Credit parked on the elements that future expensive operations will touch; the non-negativity rule means nothing ever owes more than it holds.

Stored credit is imaginary accounting, never a real allocation or runtime overhead. Its only job is to make the proof go through — choose where it sits cleverly and the analysis becomes almost mechanical.

Also called
prepaid creditcredit預付存款信用