amortized analysis – dandan's blog

Quote from Introduction to Algorithms.

In an amortised analysis, we average the time required to perform a sequence of data-structure operations over all the operations performed.

The potential method of amortised analysis represents the prepaid work as “potential energy”, or just “potential”, which can be released to pay for future operations. We associate the potential with the data structure as a whole rather than with specific objects within the data structure.

The potential method works as follows. We will perform $n$ operations, starting with an initial data structure $D_0$ . For each i=1,2,…,n, we let $c_i$ be the actual cost of the $i$ th operation and $D_i$ be the data structure that results after applying the $i$ th operations to the data structure $D_{i-1}$ . 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})$ (1)

The amortised cost of each operation is therefore its actual cost plus the change in potential due to the operation. By equation (1), the total amortised cost of the $n$ operation is

$\sum^n_{i=1}\hat{c_i}=\sum^n_{i=1}(c_i+\Phi(D_i)-\Phi(D_{i-1}))$

$= \sum^n_{i=1}c_i+\Phi(D_n)-\Phi(D_0)$

Consider an extensible array that can store an arbitrary number of integers. Each add operation inserts a new element after all the elements previously inserted. If there are no empty cells left, a new array of double the size is allocated, and all the data from the old array is copied to the corresponding entries in the new array. For instance, consider the following sequence of insertions, starting with an array of length 1: Screen Shot 2018-10-18 at 21.43.05

The table is doubled in the second, third, and fifth steps. As each insertion takes O(n) time in the worst case, a simple analysis would yield a bound of $O(n^2)$ time for n insertions. But it is not this bad. Let’s analyze a sequence of n operations using the potential method.

Suppose we can define a potential function $\Phi$ on states of a data structure with the following properties:

$\Phi(h_0)=0$ , where $h_0$ is the initial state of the data structure.
$\Phi(h_t)\geq 0$ for all states $h_t$ of the data structure occurring during the course of the computation.

Intuitively, the potential function will keep track of the precharged time at any point in the computation. It measures how much saved-up time is available to pay for expensive operations. It is analogous to the bank balance in the banker’s method. But interestingly, it depends only on the current state of the data structure, irrespective of the history of the computation that got it into that state.

We then define the amortised time of the operation as

$c+\Phi(h')-\Phi(h)$ ,

where $c$ is the actual cost of the operation and $h$ and $h'$ are the states of the data structure before and after the operation, respectively. Thus the amortised time is the actual time plus the change in potential. Ideally, $\Phi$ should be defined so that the amortised time of each operation is small. Thus the change in potential should be positive for low-cost operations and negative for high-cost operations.

Now consider a sequence of $n$ operations taking actual times $c_0, c_1, c_2, ..., c_{n-1}$ and producing data structures $h_1, h_2, ..., h_n$ starting from $h_0$ . The total amortised time is the sum of the individual amortised times:

$(c_0+\Phi(h_1)-\Phi(h_0))+(c_1+\Phi(h_2)-\Phi(h_1))+...+(c_{n_1}+\Phi(h_n)-\Phi(h_n-1)) =c_0+c_1+...+c_{n-1}+\Phi(h_n)-\Phi(h_0)=c_0+c_1+...+c_{n-1}+\Phi(h_n)$ .

Therefore the amortised time for a sequence of operations overestimates of the actual time by $\Phi(h_n)$ , which by assumption is always positive. Thus the total amortised time is always an upper bound on the actual time.

For dynamically resizable arrays with resizing by doubling, we can use the potential function

$\Phi(h)=2n-m$ ,

where $n$ is the current number of elements and $m$ is the current length of the array. If we start with an array of length 0 and allocate an array of length 1 when the first element is added, and thereafter double the array size whenever we need more space, we have $\Phi(h_0)$ and $\Phi(h_t)\geq 0$ for all $t$ . The latter inequality holds because the number of elements is always at least half the size of the array.

Now we would like to show that adding an element takes amortised constant time. There are two cases.

If $n<m$ , then the actual cost is 1, $n$ increased by 1, and $m$ does not change. Then the potential increase by 2, so the amortised time is 1+2 = 3.
If $n=m$ , then the array is doubled, so the actual time is $n+1$ . But the potential drops from $n$ to 2, so amortised time is $n+1+(2-n)=3$ .

In both cases, the amortised time is O(1).

Tag: amortized analysis

Amortized Analysis-Potential Method