Case Setup

Let s_t-1 and s_t be the size functions just before and after the step. Let y be the parent of x and z be the parent of y (if it exists).

We'll define the amortized cost to be $3(\log s_{t}(x)- \log s_{t-1}(x))+1$ for Zig and $3(\log s_{t}(x)- \log s_{t-1}(x))$ for the other cases. The amortized cost for a sequence of h steps splaying x up the tree, therefore, is

$$\sum_{t=1}^{h-1} 3(\log s_t(x)- \log s_{t-1}(x)) + 3(\log s_h(x)- \log s_{h-1}(x))+1 = 3(\log s_h(x) - \log s_0(x)) + 1.$$

This is $O(\log n)$. Why?

This means that our amortized cost for each complete splay is $O(\log n)$, even if we start deep in the tree. The intuition is that, the only way we could make the tree that deep in the first place is to have performed operations that increase the potential substantially. So, the average still works out.