On Searching a Table Consistent with Division Poset

الأصل · EN

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