# The validity of the potential function for splay tree

The paper "Self-Adjusting Binary Search Trees" defines (Page 658) the potential function for analyzing the amortized cost of a sequence of $$m$$ splay operations as the sum of the ranks of all nodes in the splay tree, where the rank of a node $$x$$ is taken as the logarithm of the size ($$s(x)$$; i.e., number of nodes in) of the subtree rooted at $$x$$:

$$\Phi(T_i) = \sum_{x \in T} \log (s(x)).$$

To make sure that the amortized cost is an upper bound of the actual cost, it is required that the final potential is no less than the initial potential $$\Phi(T_0)$$ (Page 657):

$$\forall 1 \le i \le m: \Phi(T_i) \ge \Phi(T_0).$$

Problem: How to verify the condition above? (I did not find the argument in the paper.) Maybe it is not necessary to verify this condition; if so, why?

We don't have to verify $$\forall 1 \le i \le m: \Phi(T_i) \ge \Phi(T_0).$$ This condition is a special case of a more general one, which we need to verify for this example.

Consider a data structure $$D$$ and its states $$D_0 \cdots D_m$$ produced by a sequence of $$m$$ operations $$o_1 \cdots o_m$$: $$D_0,\; o_1,\; D_1,\; o_2,\; \cdots,\; \underbrace{D_{i-1},\; o_{i},\; D_{i}}_{\text{the i-th operation}},\; \cdots,\; D_{m-1},\; o_{m},\; D_{m}.$$

The amortized cost of the $$i$$-th operation $$o_i$$ is defined as: $$\hat{c_i} = c_i + \Big(\Phi(D_{i}) - \Phi(D_{i-1})\Big)$$

Therefore, the total actual cost of these $$m$$ operations equals the total amortized cost plus the net decrease in potential from the initial to the final state.

$$\sum_{1 \le i \le m} c_i = \left( \sum_{1 \le i \le m} \hat{c_i} \right) + \Big(\underbrace{\Phi(D_{0}) - \Phi(D_m)}_{\text{net decrease in potential}} \Big).$$

For each upper bound $$\Box$$ for $$\Phi(D_{0}) - \Phi(D_m)$$, we get a corresponding upper bound for the total actual cost of all operations:

$$\sum_{1 \le i \le m} c_i \le \left( \sum_{1 \le i \le m} \hat{c_i} \right) + \Box.$$

The condition $$\forall 1 \le i \le m: \Phi(D_i) \ge \Phi(D_0)$$ in the post is just a special case of deriving upper bounds for the total actual cost, where the upper bound is the total amortized cost. Moreover, it is common to choose $$\Phi$$ such that $$\Phi(D_0) = 0$$ and $$\Phi(D_i) \ge 0$$ for all $$i$$.

To verify the validity of the potential function for splay trees, we use the following upper bound for $$\Phi(T_{0}) - \Phi(T_i)$$:

$$\Phi(T_{0}) - \Phi(T_i) \le n \log n.$$