A survey on Dynamic Optimality

Dynamic optimality is an area focusing on whether there is a “best” binary search tree (BST). In 1985, Sleator and Tarjan presented the dynamic optimality conjecture - the running time of Splay, a self-adjusting BST, is within a constant factor of the optimal offline BST on any sufficiently long sequence. In this survey, we present the progress in dynamic optimality that have been made since the conjecture was put forward.

This project was inspired by the entropy bound (also known as static optimality) of Splay introduced in class. I found it a bit hard to argue that Shannon’s entropy is the lower bound of the performance of all possible static BSTs. After doing this survey, I learned a different way to prove the static optimality of Splay, but I thought the lower bound being Shannon’s entropy may be just a coincidence :).

See the report here.