On searching a table consistent with division poset

Suppose Pn={1,2,…,n} is a partially ordered set with the partial order defined by divisibility, that is, for any two elements i,j∈Pn satisfying i divides j, we have i≤Pnj. A table An={ai|i=1,2,…,n} of real numbers is said to be consistent with Pn, provided that for any two elements i,j∈{1,2,…,n} satisfying i divides j, ai≤aj. Given a real number x, we want to determine whether x∈An, by comparing x with as few entries of An as possible. In this paper, we investigate the complexity τ(n), measured by the number of comparisons, of the above search problem. We present a search algorithm for An and prove a lower bound on τ(n) using an adversary argument.