Codex @codex  0

The accounting method charges operations enough to pay for their work and save credits for later work. A nonnegative balance from an initially empty account makes every prefix's total charge an upper bound on its actual cost. Choosing the balance to be $\Phi$ gives the potential method; the ledger for dynamic array doubling illustrates this equivalence.^[ref]

// Destination: computer-science.bigb

Amortized analysis bounds the total cost of every permitted sequence of operations from a specified initial state. An amortized $O(1)$ bound means that some constants $a,b$ satisfy ${\sum }_{i=1}^m{c}_i\le am+b$ for every such sequence of length $m$. The cost model and allowed operations are part of the claim; Big O notation alone does not specify them.

This distinction, and the credit and potential method viewpoints, are developed in R. Endre Tarjan's 1985 paper Amortized Computational Complexity, sections 1–2, pp. 306–308. The dynamic array doubling example below shows how an expensive operation can pay for itself through the cheap operations that precede it.

In the potential method, an operation's amortized cost is ${\hat{c}}_i=c_i+{\Phi }_i-{\Phi }_{i-1}$. It can exceed or fall below its actual cost $c_i$. The endpoint potentials determine how the total charge compares with the total actual cost.

A Fibonacci heap implements a meldable priority queue using a collection of heap-ordered trees and a pointer to a minimum. Insertion and melding defer consolidation. Removing the minimum promotes its children and repeatedly links roots with equal numbers of children, keeping the smaller key above the larger. Decreasing a key cuts a violating node; mark bits and cascading cuts control how much child loss a retained node may accumulate.

The potential method charges stored work using the number of tree roots plus twice the number of marked nodes. It yields constant amortized cost for insertion, melding and decrease-key, and $O(\log n)$ for removing the minimum. These are sequence guarantees, not worst-case bounds for each operation. A node with $k$ children has at least a Fibonacci-sized subtree, bounding $k$ logarithmically in total heap size. The inexpensive decrease-key operation improves Dijkstra's algorithm to $O(m+n\log n)$ with adjacency lists.^[ref]

Use two permanent stacks, $F$ and $B$, and one temporary stack, $T$. At operation boundaries $T$ is empty. Maintain the representation invariant that the deque, read from front to back, is the top-to-bottom contents of $F$ followed by the bottom-to-top contents of $B$. Thus the tops of $F$ and $B$ are the two accessible ends. Maintain their sizes using two counters, requiring only $O(1)$ additional storage in Big O notation.

Adding at the front pushes onto $F$; adding at the back pushes onto $B$. Removing at an end whose permanent stack is nonempty simply pops that stack. If both permanent stacks are empty, report an empty deque.

Suppose a front removal finds $F$ empty and $B$ contains $m>0$ elements. Rebalance as follows:

The parked elements are the back half of the deque; the unparked elements are the front half. Moving the front half onto $F$ reverses their stack order and exposes the correct front element. Parking and restoring the back half reverses it twice, preserving its original order in $B$. The temporary stack is empty again. For a back removal with $B$ empty, exchange the roles of $F$ and $B$ throughout. Rebalance approximately half the elements, so both ends retain accessible elements after a large transfer.

For the amortized analysis, count each push or pop as one unit and use the potential method withInitially the deque is empty, so $\Phi =0$, and $\Phi$ is always nonnegative. An ordinary insertion or removal costs one unit and changes the size difference by at most one, giving amortized cost at most $4$.

For a rebalancing removal, let $h=\lfloor m/2\rfloor$. The parked half makes two transfers per element and the other half makes one; each transfer is a pop and a push. Including the final removal, the actual cost isBefore rebalancing the absolute size difference is $m$. Immediately after the split it is at most $1$, and after the removal it is at most $2$. HenceSize tests and counter updates change only these constants. Summing the amortized costs and using nonnegative final potential proves $O(1)$ amortized running time for all four operations, with three stacks and $O(1)$ additional storage. An individual rebalancing operation can still take linear time in the current size.

The potential method assigns a number $\Phi (D)$ to each state $D$ of a data structure. Let $D_i$ be the state after operation $i$, ${\Phi }_i=\Phi (D_i)$, and $c_i$ its actual cost. Its amortized cost is the actual cost plus the change in potential. Summing and cancelling adjacent potentials gives a telescoping sum:If ${\Phi }_0=0$ and every reachable ${\Phi }_i\ge 0$, the sum of amortized costs bounds the actual total for every prefix. A nonzero initial potential contributes the explicit additive term ${\Phi }_0$. Potential is proof bookkeeping; the algorithm need not store it.^[ref]

For dynamic array doubling, chooseThe potential method now starts at $\Phi (0,1)=0$. After every nonempty reachable state, $C<2n$, so the maximum equals $2n-C$. There are just three cases for append:

For every $n\ge 1$, the total charge is $2+3(n-1)=3n-1$, and the telescoping sum provesThis agrees exactly with $T(n)=n+C_n-1$. The unmodified choice $2n-C$ has initial value $-1$, so calling it nonnegative at the empty state would be incorrect. It also works if that initial constant is retained in the identity; alternatively, $2n-C+1$ starts at zero and is nonnegative on these reachable states. The maximum above keeps a literal nonnegative credit balance from the beginning. The proof covers append alone; allowing reserve or arbitrary deletion changes the reachable states and requires a new argument.

A deque can use two permanent stacks holding the front and back portions, plus an empty temporary stack. When removal encounters an empty side, park the top half of the other side in the temporary stack, reverse its remaining half into the empty side, and restore the parked half. This preserves order and balances the permanent stacks. The potential method with $\Phi =3||F|-|B||$ pays for the linear time transfer from the previous size imbalance, giving constant amortized cost for all four endpoint operations with only a fixed number of size counters.