More Nearly Optimal Algorithms for Unbounded Searching, II:The Transfinite 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 ) = Y$ then $F(n ) = Y$ for all $n > n_0 $, the unbounded search problem is to use tests of the form “is $F(i) = X$?*#821; to determine the smallest n such that $F(n) = 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 In Part I of this paper it is shown how to construct an infinite sequence of algorithms, each of which is much closer to optimality than its predecessor. Diagonalizing over this sequence yields a new algorithm that is far better than any of the algorithms in the sequence: this “omega-th” algorithm 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. In this paper the construction techniques are generalized to get dramatically better algorithms and lower bounds ad infinitum. Specifically, for each ordinal $\iota < \epsilon _0 $, an algorithm is given that is dramatically closer to optimality than the algorithm corresponding to a smaller ordinal. All algorithms constructed for t Eo are proved to be optimal in a strong sense. Parallel results for the asymmetric case are also given.