Fundamental Potential Function Inequality

We've got a sequence of k operations. Di is the state of the computation after i operations. D0 is the initial program state.

\begin{eqnarraystar} \sum_{i=1}^k c_i &\le& \sum_{i=1}^k (\hat{c}_i + \Phi(D_{i... ...+ \ldots \ &=& \sum_{i=1}^k \hat{c}_i + \Phi(D_0) - \Phi(D_k)\end{eqnarraystar}

next up previous
Next: Using the Inequality Up: POTENTIAL FUNCTION ANALYSIS Previous: Amortized Cost