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 &pgr;/2 times that of the optimal order and this bound is 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.
self-organization search paper general timing heuristics optimality order class case