Entire Splay

Repeating this analysis for each pair of rotations as we go up, plus the final single rotation if needed, we get a total amortized cost of $3(\log n - \log s_0(x)) + 1 = O(\log n)$, where the potential function inequality is satisfied (string them all together).

Therefore, a splay operation in a tree of size n has an amortized cost of $O(\log n)$. So, a sequence of k splays will cost $O(k \log n)$.


next up previous
Up: ANALYSIS OF SPLAY TREES Previous: Zig-Zig Case