Dynamic Optimality Conjecture:[REF] Let A be any binary search tree algorithm that accesses an element x by traversing the path from the root to x at a cost of d(x)+1, and that between accesses can make any rotations in the tree at a cost of 1 per rotation.
Deque Conjecture:[REF][REF][REF] Let S be a sequence of m double-ended queue operations (push, pop, inject, eject).