#online-algorithms

For a sequence $S$ of accesses to keys in a binary search tree with $n$ keys, let $\mathrm{OPT}(S)$ be the minimum total cost of serving $S$ by any binary search tree algorithm that may rotate the tree, even one that knows $S$ in advance. Prove or disprove that splay trees serve every access…