1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ "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$. $\endgroup$ – Raphael Sep 5 '16 at 13:34
2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.