Amortized analysis and the potential method

Question

To my understanding to use the potential method to get the amortized cost of an operation the following conditions need to be satisfied:

• $\Phi (D_{0}) = 0$
• $\Phi (D_{i}) \geq 0$ for all $i \geq 0$
• $\Phi (D_{i}) = \Phi (D_{i-1}) + \operatorname{cost}_{\text{am}}(op_{i}) - \operatorname{cost}_{\text{real}}(op_{i})$

However, I'm seeing a solution to a problem that has a potential function such that $\Phi (D_{0}) \ne 0$. How could this still work?

Answer 1

The initial potential, per se, doesn't really matter. The important part is the interaction between the first two rules: the potential is never allowed to drop below its initial value (except perhaps in the middle of an operation).

Edit:

The technique being used does not appear to be quite the same sort of amortized analysis you're thinking of that guarantees that any sequence of $k$ operations will take no more than $\sum a_i [0<i\le k]$ real time. Rather, a very specific sequence of a specific number of operations is being performed. This allows certain things to be done in the analysis that would otherwise be forbidden. Note that the extra $n$ is tacked on to the total time at the end, in the second hint.