Self-organizing sequential search and Hilbert's inequalities

摘要

In this paper we describe a general technique which can be used to solve an old problem in analyzing self-organizing sequential search. We prove that the average time required for the move-to-front heuristic is no more than n/2 times that of the optimal order and this bound is the best possible. Hilbert's inequalities will be used to derive large classes of inequalities some of which can be applied to obtain tight worst-case bounds for several self-organizing heuristics.