On the Competitiveness of Linear Search

Ian Munro

University of Waterloo

Fri Jan 30 15:10:00 NZDT 2004 in Room 031, MSCS

Abstract

We re-examine offline techniques for linear search. Under a reasonable model of computation, a method is given to perform offline linear search in amortized cost proportional to the entropy of the request sequence. It follows that no online technique can have an amortized cost of that which one could obtain if given the request sequence in advance, i.e., there is no competitive linear search algorithm.