On Searching a Table Consistent with Division Poset

Abstract

Suppose $P_n=\{1,2,...,n\}$ is a partially ordered set with the partial order defined by divisibility, that is, for any two distinct elements $i,j\in P_n$ satisfying $i$ divides $j$, $i{<}_{P_n}j$. A table $A_n=\{a_i|i=1,2,...,n\}$ of distinct real numbers is said to be \emph{consistent} with $P_n$, provided for any two distinct elements $i,j\in \{1,2,...,n\}$ satisfying $i$ divides $j$, $a_i<a_j$. Given an real number $x$, we want to determine whether $x\in A_n$, by comparing $x$ with as few entries of $A_n$ as possible. In this paper we investigate the complexity $\tau (n)$, measured in the number of comparisons, of the above search problem. We present a $\frac{55n}{72}+O({\ln }^{2}n)$ search algorithm for $A_n$ and prove a lower bound $(3/4+17/2160)n+O(1)$ on $\tau (n)$ by using an adversary argument.

16 pages, no figure; same results, representation improved, add references