The Greedy Binary Search Tree is Non-trivially Competitive

Yuhao Guo, Seth Pettie, Daniel Skora +1

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…