In amortized analysis, we can show that the average cost of an operation. An amortized analysis guarantees the average performance of each operation in the worst case.

Three common techniques used in amortized analysis: aggregate analysis, accounting method, potential method.

Data Structural Definition

We will use Stack and Binary Counter as an example for demonstrating three techniques.

Stack

Firstly, we will define the Stack operations:

\(PUSH(S, x)\): pushes object \(x\) onto stack \(S\).

\(POP(S)\): pops the top of stack \(S\) and returns the popped object. Calling POP on an empty stack generates an error.

\(MULTIPOP(S,k)\): pop the top of stack \(S\) and returns the popped object \(k\) times. If POP an empty stack, generate an error.

def MULTIPOP(S, k):
    while not STACK_EMPTY(S) and k > 0:
        POP(S)
        k = k - 1

Binary Counter

The Binary Counter can be defined as follows:

We use an array \(A[0,..,k-1]\)of bits, where \(A.length = k\) as the counter. Therefore, the binary number \(x =\sum_{i=0}^{k-1}A[i]\cdot 2^i\).

\(INCREMENT(A)\): add 1 to the value in the counter.

def INCREMENT(A):
    i = 0
    while i < A.length and A[i] == 1:
        A[i] = 0
        i = i + 1
    if i < A.length:
        A[i] = 1

Aggregate Analysis

The aggregate analysis shows that for all \(n\), a sequence of \(n\) operations takes worst-case time \(T(n)\) in total. In the worst case, the average cost, or amortized cost, per operation is \(T(n)/n\).

Stack

Using the previous analysis method, we will figure out that the MULTIPOP takes \(O(n)\) times, and other two operations take \(O(1)\).

However, using the aggregate analysis, we can obtain a better upper bound solution. We can determine that PUSH, POP and MULTIPOP operations on an initially empty stack can cost at most \(O(n)\), since you have to push something before pop up everything.

Therefore, the average cost of an operation is \(O(n)/n=O(1)\). In other words, all three stack operations have an amortized cost of \(O(1)\).

Binary Counter

In incrementing a binary counter, we need to consider how many time the flipping occurs. From the figure illustrated below, we can find out that \(A[0]\) does flip each time, \(A[1]\) does flip \(\lfloor n/2\rfloor\), and \(A[2]\) flips \(\lfloor n/4\rfloor\)... In general, for \(i = 0,1,...,k-1\), bit \(A[i]\) flips \(\lfloor n/2^i\rfloor\) times in a sequence of \(n\) INCREMENT operations on an initially zero counter.

Thus, \[ \sum_{i=0}^{k-1}\left\lfloor \frac{n}{2^{i}}\right\rfloor < n\sum_{i=0}^{\infty} \frac{1}{2^i}=2n \] Therefore, the total time on an initially zero counter is \(O(n)\). The average cost of each operation is \(O(n)/n=O(1)\).

Accounting Method

We denote the actual cost of the \(i^{th}\) operation by \(c_i\) and the amortized cost of the \(i^{th}\) operation by \(\hat{c_i}\), we require \[ \sum_{i=1}^n\hat{c_i}\geqslant \sum_{i=1}^nc_i \] The total credit stored in the data structure is the difference between the total amortized cost and the total actual cost, or \(\sum_{i=1}^n\hat{c_i}- \sum_{i=1}^nc_i\). The total credit should be nonnegative at all times.

Stack

The actual cost of the operation were:

where \(k\) is the argument supplied to MULTIPOP and \(s\) is the stack size when it is called.

The amortized cost should be like this:

Potential Method

The potential method of amortized analysis represents the prepaid work as "potential energy". It is similar to the physical terminology which could represent the amortized cost.

We denote that a potential function \(\Phi\) maps each data structure \(D_i\) to a real number \(\Phi (D_i)\), which is the potential associated with data structure \(D_i\).

The amortized cost \(\hat{c_i}\) of the \(i^{th}\) operation with respect to potential function \(\Phi\) is defined by \[ \hat{c_i}=c_i+\Phi(D_i)-\Phi(D_{i-1}) \] Therefore, the amortized cost is actual cost plus the changes in potential due to the operation. \[ \begin{equation} \begin{aligned} \sum_{i=1}^n \hat{c_i}&=\sum_{i=1}^n(c_i+\Phi(D_i)-\Phi(D_{i-1})) \\ &=\sum_{i=1}^n c_i+\Phi(D_n)-\Phi(D_{0}) \end{aligned} \end{equation} \]

Stack Operations

For the empty stack \(D_0\) with which we start, we have \(\Phi(D_0)=0\). Since the number of objects in the stack is never negative, we have \[ \begin{equation} \begin{aligned} \Phi(D_i) &\geqslant 0=\Phi(D_0) \end{aligned} \end{equation} \]

PUSH

If the \(i\)th operation on a stack containing \(s\) objects is a PUSH operation, then the potential difference is \[ \Phi(D_i)-\Phi(D_{i-1})=(s+1)-s=1 \] Therefore, the amortized cost of PUSH operation is \[ \begin{equation} \begin{aligned} \hat{c_i}&=c_i+\Phi(D_i)-\Phi(D_{i-1})\\&=1+1\\&=2 \end{aligned} \end{equation} \]

MULTIPOP

If the \(i^{th}​\) operation on the stack is MULTIPOP, it will cause \(k^\prime =\min(k,s)​\) objects to be popped off the stack. The actual cost of the operation \(c_i​\) is \(k^\prime ​\) as well.

Therefore, the potential difference is \(\Phi(D_i)-\Phi(D_{i-1})=-k^\prime\).

As a result, the amortized cost of the MULTIPOP operation is \[ \begin{equation} \begin{aligned} \hat{c_i}&=c_i+\Phi(D_i)-\Phi(D_{i-1})\\&=k^\prime-k^\prime\\&=0 \end{aligned} \end{equation} \] The POP operation is similar whose amortized cost is also \(\hat{c_i}=0\).

Binary Counter

As a programmer, I don't have such instinct to determine the amortized cost of binary counter using accounting method... However, we can interpret it using potential method easily.

We define the potential of the counter after the \(i\)th INCREMENT operation to be \(b_i\), the \(i\)th INCREMENT operation resets \(t_i\) bits.

The actual cost of the operation is therefore at most \(t_i+1\). If \(b_i=0\), then the \(i\)th operation resets all \(k\) bits, and \(b_{i-1}=t_i=k\). If \(b_i>0\), then \(b_i=b_{i-1}-t_i+1\). Therefore, \(b_i\le b_{i-1}-t_i+1\), and the potential difference is \[ \Phi(D_i)-\Phi(D_{i-1}) \le (b_{i-1}-t_i+1)-b_{i-1}=1-t_i \] The amortized cost is \[ \begin{equation} \begin{aligned} \hat{c_i}&=c_i+\Phi(D_i)-\Phi(D_{i-1})\\&\le(t_i+1)+(1-t_i)\\&=2 \end{aligned} \end{equation} \]