More Nearly Optimal Algorithms for Unbounded Searching, Part I: The Finite Case
Edward M. Reingold, Xiaojun Shen · SIAM Journal on Computing · 1991
Given a function $F:N^ + \to \{ X,Y\} $ with the property that if $F(n_0 ) = {\text{Y}}$ then $F(n) = {\text{Y}}$ for all $n > n_0 $, the unbounded search problem is to use tests of the form “is $F(i) = {\text{X}}$?” to determine the smallest n such that $F(i) = {\text{Y}}$; the “cost” of a search algorithm is a function $c(n)$, the number of such tests used when the location of the first Y is n. A solution to this search problem specifies a prefix-free, binary encoding of the positive integers in which the cost $c(n)$ is the number of bits used to encode n It is shown that the “ultimate algorithm,” of Bentley and Yao [Inform. Process. Lett., 5 (1976), pp. 82–87], which is within an additive $\Theta (\lg ^ * n)$ factor of a lower bound on the cost of this problem, is “far” from optimal in the sense that it is just the second in an infinite sequence of search algorithms, each of which is much closer to optimality than its predecessor. A corresponding sequence of lower bounds is also given, based on Kraft’s inequality, each of which is much stronger than its predecessor. Diagonalizing over this sequence of search algorithms yields an algorithm, which is given explicitly in a Pascal-like notation, that is within an additive factor of $\alpha (n) + 2$ of the corresponding lower bound, where $\alpha (n)$ is a functional inverse of Ackermann’s function—an extremely slowly growing function. For each search algorithm, the corresponding prefix-free, binary encoding of the integers is given, together with the decoding algorithm. Finally, algorithms/encodings are constructed that differ from the lower bounds by only negligible amounts even for the asymmetric case in which the cost of a Y answer and the cost of an X answer are not the same. In Part II it is shown how to continue the construction to get a transfinite sequence of dramatically better algorithms/encodings and lower bounds.