Amortized analysis (${\hat{c}}_i=c_i+{\Phi }_i-{\Phi }_{i-1}$)

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.

For an initially zero $k$-bit binary counter, suppose changing bit $i$ costs $2^i$. It changes exactly $\lfloor n/2^i\rfloor$ times in $n$ increments. Consequently the total is $\Theta (n\min \{k,1+{\log }_{2}n\})$ for $n,k\ge 1$. The upper bound counts at most $n$ cost at each active position; the lower bound uses $\lfloor x\rfloor \ge x/2$ for $x\ge 1$. This shows why exponential position costs cancel the decreasing carry frequencies that make the ordinary binary counter have constant amortized cost.

An amortized analysis can bound the total time complexity $T(m,n)$ of every allowed sequence of $m$ operations by $ma(n)+I(n)$, where $n$ is a size parameter and $I(n)$ accounts for initialization or the specified initial state. The bound $a(n)$ is then an amortized per-operation time complexity. Dividing the total bound by $m$ explains the averaging; it is a guarantee over every permitted sequence, without an assumed probability distribution on requests. Individual operations can cost more than $a(n)$.

Consider a dynamic array holding fixed-size entries. Its size $n$ is the number of occupied slots and its capacity $C$ is the number of allocated slots. Start with $n=0$, $C=1$. The only operation is append: if $n=C$, allocate a new array of capacity $2C$, copy the $C$ existing entries, and release the old array; then write the new entry and increase $n$ by one. There is no reserve operation, deletion or shrinking in this model.

Count one unit for writing the new entry and one unit per existing entry copied during resizing. Thus the $i$th append has actual cost $c_i=1$ without resizing and $c_i=C+1$ when the old capacity $C$ is full. Copying an entry, including its read and write, is one counted action. Allocation, deallocation, index arithmetic operations and the initial one-slot allocation are outside this exact count. If these add only a constant per ordinary append and a linear cost per resize, the Big O notation conclusions still hold, with different constants; costly entry copies require their own cost model.

The first ten costs are $1,2,3,1,5,1,1,1,9,1$. For example, append $9$ copies eight entries and writes one, so $c_9=9$. At that point the capacity becomes $16$, but the total cost of all nine appends is only $24$.

For $n\ge 1$, the final capacity is $C_n=2^{\lceil {\log }_{2}n\rceil }$. Every earlier capacity $1,2,4,\dots ,C_n/2$ was copied once. This geometric series sums to $C_n-1$, including the empty sum when $n=1$. Therefore aggregate analysis gives the exact totalConsequently $T(n)<3n$, so append has amortized $O(1)$ cost in Big O notation for every prefix from this empty initial state. The values being appended do not affect the count. In contrast, an append to a full dynamic array with $n$ entries costs $n+1$: its worst-case cost is $O(n)$, and actually grows linearly along full-capacity states. A bound on total work does not promise a constant response time for each call.

The same policy controls computer memory: after each completed append, $n\le C_n<2n$ for $n\ge 1$, so fewer than $n$ slots are unused. This is a bound on the retained backing array, with fixed-size slots. During a resize from full capacity $k$ to $2k$, a copying implementation can temporarily hold both arrays, totalling $3k$ allocated slots before releasing the old one. Thus the retained-capacity bound does not bound this temporary peak by twice the live size. Allocator metadata and separately allocated objects are additional computer memory costs.

The geometric series is the source of the efficiency. If capacity instead increases by one each time, the same count becomes $n+1+2+\cdots +(n-1)=n(n+1)/2$, a quadratic total. Dynamic array doubling buys a linear total with bounded spare capacity, even when the final length is unknown.

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.

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.

Aggregate analysis bounds the total cost of a whole sequence directly, then divides by its length to obtain an amortized bound. Summing the copied capacities as a geometric series in dynamic array doubling is an example.

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