No more lunch: analysis of sequential search
Thomas M. English · 2004
Sequential search algorithms of the type predicated in conservation theorems are studied in their own right. With representation of functions as strings, the sets of test functions and search results are identical. This allows sequential search algorithms to be treated as operators on distributions on functions. Certain distributions, referred to as block uniform, are fixed points for all algorithms. Sequential search preserves the identity of the nearest fixed point and the Kullback-Leibler distance to that point. In practice, distributions of test functions are not block uniform and conservation properties hold to a degree that depends upon distance to the nearest fixed point. Randomized sequential search is also analyzed. Here the search operator generally moves the distribution closer to the nearest fixed point, reducing the potential for poor quality by some measure.