The cost of offline binary search tree algorithms and the complexity of the request sequence

In evaluating the performance of online algorithms for search trees, one wants to compare them to the best offline algorithm available. In this paper we lower bound the cost of an optimal offline binary search tree using the Kolmogorov complexity of the request sequence. We obtain several applications for this result. First, any offline binary search tree algorithm can be at most a constant factor away from the entropy of the process producing the request sequence. Second, for a fraction 1−1/2m of request sequences of length m on n items the cost of any offline algorithm is Ω(m(logn−1)). Third, the expected cost of splay trees is within a constant factor of the expected cost of an optimal offline binary search tree algorithm in a subset of Markov chains.