It Works!

We need to show that the fundamental inequality of potential functions holds:

$\begin{displaymath} \hat{c}_t + \Phi(x_{t-1}) - \Phi(x_t) \ge c_t.\end{displaymath}$

$\begin{eqnarraystar} \lefteqn{\hat{c}_t + \Phi(x_{t-1}) - \Phi(x_t)}\ &=& 2 + \... ...=& 1 + \mbox{number of trailing zeros in $x_{t-1}$} \ &=& c_t\end{eqnarraystar}$

Note that the potential function measures the amount of work that went into building the data structure.

Next: ANALYSIS OF SPLAY TREES Up: AMORTIZED ANALYSIS Previous: Potential Function