Dynamic Optimality—Almost
Erik D. Demaine, Dion Harmon, John Iacono, Mihai Ptraşcu · SIAM Journal on Computing · 2007
We present an $O(\lg \lg n)$‐competitive online binary search tree, improving upon the best previous (trivial) competitive ratio of $O(\lg n)$. This is the first major progress on Sleator and Tarjan’s dynamic optimality conjecture of 1985 that $O(1)$‐competitive binary search trees exist.