Analysis Setup

Here's the setup for the analysis. First, define the size of a node x to be the number of nodes in the subtree rooted at x.

• A unit of work is a rotation.
• A splay at some node x up to the root r is the operation, and its amortized cost is $3(\log s(r)- \log s(x))+1$.
• The potential function for a tree T is $\Phi(T) = \sum_{x\in T} \log(s(x))$.

We need to show that the operation of splaying a node x to the root satisfies the potential function inequality. We'll do this one case at a time.