Why do we need "potential” for amortized analysis?

Question

In the current version as of the Wikipedia article “Potential method”, the amortized cost of each operation is defined as the following $$ T_{\mathrm{amortized}}(o) = T_{\mathrm{actual}}(o) + C \cdot (\Phi(S_{\mathrm{after}}) - \Phi(S_{\mathrm{before}})), $$

and the total amortized cost is $$ \begin{align*} T_{\mathrm{amortized}}(O) &= \sum_i (T_{\mathrm{actual}}(o_i) + C \cdot (\Phi(S_{i+1}) - \Phi(S_{i}))) \\ &= T_{\mathrm{actual}}(O) + C \cdot (\Phi(S_{\mathrm{final}}) - \Phi(S_{\mathrm{initial}})). \end{align*} $$

I understand the formulas and understand $T_{\mathrm{amortized}}$ is an upper bound on $T_{\mathrm{actual}}$ if the initial potential is zero. And I think I understand the basic examples like "binary counter", "two stack FIFO", etc. However, I am puzzled this:

The actual cost is part of the formula.

I might be wrong but it looks like the actual cost is a known quantity. If we already know the actual cost, why do we need to add the "potential" to get an upper bound? It looks useless to me. Can anyone help give an example in which such "potential analysis" is useful?

Answer 1

As is unfortunately sometimes the case, Wikipedia is doing a terrible job of explaining what amortized analysis actually is.

The idea of amortized analysis is that while operations may have a bad worst case cost, their average cost could be much lower. Average cost means different things in different circumstances. In amortized analysis, here is what it means:

Suppose that you have a data structure supporting operations $O_1,\ldots,O_r$. We say that these operations have amortized cost $c_1,\ldots,c_r$ if the cost of the sequence $O_{i_1},\ldots,O_{i_n}$ of operations is at most $$ c_{i_1} + \cdots + c_{i_n}. $$

This definition is a bit simplistic, since sometimes the amortized cost depends on other auxiliary parameters such as the overall number of operations or the number of operations of a specific type.

The potential method is one way of carrying out amortized analysis, that is, of proving that the operations in a certain data structure have some amortized cost. Stated differently, if you want to prove that the amortized cost of $O_1,\ldots,O_r$ is $c_1,\ldots,c_r$, then one of the techniques is the potential method. There are other techniques as well.

How does the potential method work? You define a potential function $\Phi$ on the state of the data structure. The potential function must be always non-negative, and for the initial data structure it must be zero. You then prove that if at state $S_{\text{before}}$ you execute operation $O_i$ which leads to state $S_{\text{after}}$, then the cost $T_{\text{actual}}$ of the operation satisfies $$ T_{\text{actual}} \leq c_i + \Phi(S_{\text{before}}) - \Phi(S_{\text{after}}). $$ Given that this holds for all $i$, consider a sequence of operations $O_{i_1},\ldots,O_{i_n}$, and denote the corresponding states of the data structure by $S_0,\ldots,S_n$. The upper bound on $T_{\text{actual}}$ implies that the total cost of these operations is at most $$ \begin{align*} \sum_{t=1}^n [c_{i_t} + \Phi(S_{t-1}) - \Phi(S_t)] &= \sum_{t=1}^n c_{i_t} + \sum_{t=1}^n [\Phi(S_{t-1}) - \Phi(S_t)] \\ &= \sum_{t=1}^n c_{i_t} + \Phi(S_0) - \Phi(S_n) \\ &= \sum_{t=1}^n c_{i_t} - \Phi(S_n) \\ &\leq \sum_{t=1}^n c_{i_t}, \end{align*} $$ which was to be proven.