# Is the potential difference in the two consecutive states of a data structure equal to the credit of the change inducing operation?

I am following CLRS for studying Amortized analysis with potential function and there I came through the following :

Let a data structure go through states : $D_0$ $D_1$ $D_2$ $....$ $D_n$ while applying operations $O_1$ $O_2$ $O_3$ $....$ $O_{n-1}$

$\therefore$ the amortized cost can be written as :

$\hat c(O_i) = c(O_i) + \phi (D_{i+1}) - \phi (D_{i})$ .

My doubt is that if the state of data structure changes from $D_{i}$ to $D_{i+1}$ that will be due to that cost of $i^{th}$operation which must be equal to the change in potential of the data structure.

So isn't $c(O_i) = \phi (D_{i+1}) - \phi (D_{i})$ ? If not, they why are they not equal ?

Is the potential difference between two states, the overwork (credit) we are doing? If this statement is true, is it the reason for the answer for my doubt to be false?

• "the amortized cost of ith operation can be written as" -- Careful. "Amortized cost" has no meaning for a single $i$. You are creating a completely artificial function $\hat{c}$. The helpful relation to $c$ appears only after summing over all $i$.
– Raphael
Sep 5, 2016 at 13:34

The potential function is a fictitious quantity which is used to bound the cost of operations in a data structure. Suppose that our data structure supports only one operation, whose worst-case cost is $C$, and that we want to show that the amortized cost is only $\hat{C}$. What we do is define quantities $\phi(D_i)$ that satisfy the following axioms:

1. $\phi(D_0) = 0$.
2. $\phi(D_n) \geq 0$ for all $n \geq 0$.
3. $\hat{c}(O_i) := c(O_i) + \phi(D_{i+1}) - \phi(D_i) \leq \hat{C}$.

We then have, for all $n \geq 0$, \begin{align*} n \hat{C} &\geq \hat{c}(O_1) + \cdots + \hat{c}(O_n) \\ &= c(O_1) + \cdots + c(O_n) + \phi(D_{n+1}) - \phi(D_0) \\ &\geq c(O_1) + \cdots + c(O_n) \, . \end{align*} In other words, the amortized cost of each operation is at most $\hat{C}$.

If we define $\phi$ via $c(O_i) = \phi(D_{i+1}) - \phi(D_i)$, then we are really defining some other fictitious quantity. A better choice from the point of view of the analysis above would actually be $\phi(D_i) = 0$, which allows us to recover the bound $C$. The general idea is that we want the fictitious potential function $\phi$ to generally be "small", but sometimes we allow it to grow (we "borrow") so that we can later on take the cost of a costly operation.

Here is a very simple example. Consider a data structure with a single operation in which operation $2^i$ costs $2^i$, and other operations cost $1$. A priori, the worst-case cost is infinite. However, suppose that we define $\phi(D_n) = 2n - 2^k$, where $2^{k-1} < n \leq 2^k$, that is, $2^k$ is the smallest power of $2$ above or at $n$ (and $\phi(D_0) = 0$). Since $n > 2^{k-1}$, when $n > 0$ we indeed have $\phi(D_n) = 2(n-2^{k-1}) > 0$.

When $2^{j-1} < i < 2^j$, we have $$\hat{c}(O_i) = 1 + [2(i+1) - 2^j] - [2i - 2^j] = 3.$$ In this case we are "borrowing", since $\hat{c}(O_i) > c(O_i)$.

When $i = 1$, we get $\hat{c}(O_1) = 1 + [2 - 1] - [4 - 2] = 0$.

When $i = 2^j > 1$, we have $$\hat{c}(O_{2^j}) = 2^j + [2(2^j+1)-2^{j+1}] - [2(2^j)-2^j] = 2.$$ In this case the potential collapses from $2(2^j) - 2^j = 2^j$ to $2(2^j+1) - 2^{j+1} = 2$, allowing us to "pay" for the costly operation $2^j$.

We conclude that the amortized cost per operation is at most $3$.