the entire splay operation, this telescopes to 3(rank(root)−rank(x)) which is O(log n). The Zig operation adds an amortized cost of 1, but there's at most one such operation. So now we know that the total amortized time for a sequence of m operations is: To go from the amortized time to the actual time, we must add the decrease in potential from the initial state before any operation is done (Φi) to the final state after all operations are completed (Φf). where the last inequality comes from the fact that for every node x, the minimum rank is 0 and the maximum rank is log(n). Now we can finally bound the actual time: Weighted analysis The above analysis can be generalized in the following way. Assign to each node r a weight w(r). Define size(r) = the sum of weights of nodes in the sub-tree rooted at node r (including r). Define rank(r) and Φ exactly as above. The same analysis applies and the amortized cost of a splaying operation is again: where W is the sum of all weights. The decrease from the initial to the final potential is bounded by: since the maximum size of any single node is W and the minimum is w(x). Hence the actual time is bounded by: Performance theorems There are several theorems and conjectures regarding the worst-case runtime for performing a sequence S of m accesses in a splay tree containing n elements. Dynamic optimality conjecture In addition to the proven performance guarantees for splay trees there is an unproven conjecture of great interest from the original Sleator and Tarjan paper. This conjecture is known as the dynamic optimality conjecture and it basically claims that splay trees perform as well as any other binary search tree algorithm up to a constant factor. Dynamic Optimality Conjecture: Let be any binary search tree algorithm that accesses an element by traversing the path from the root to at a cost of , and that between accesses can make any rotations in the tree at a cost of 1 per rotation. Let be the cost for to perform the sequence of accesses. Then the cost for a splay tree to perform the same accesses is . There are several corollaries of the dynamic optimality conjecture that remain unproven: Traversal Conjecture: Let and be two splay trees containing the same elements. Let be the sequence obtained by