The Greedy Binary Search Tree is Non-trivially Competitive

Abstract

We prove that the $\text{Greedy}$ binary search tree is $2^{O(\sqrt{\log \log n})}$-competitive. It is widely conjectured that $\text{Greedy}$ is $O(1)$-competitive, but before this work it was not known to be $f$-competitive, for any non-trivial $f(n)=o(\log n)$. Our analysis differs from prior analyses of binary search trees. It takes what might be called a "scaling" approach, where the cost at a refined scale is related to the cost at a coarser scale, and Wilber's interleave lower bound.

18 pages