On searching a table consistent with division poset
Suppose P-n = {1, 2,..., n} is a partially ordered set with the partial order defined by divisibility, that is, for any two elements i, j epsilon P-n satisfying i divides j, we have i <= p(n) j. A table A(n) = {ai vertical bar i = 1, 2,..., n} of real numbers is said to be consistent with P-n, provided that for any two elements i, j epsilon {1, 2,..., n} satisfying i divides j, a(i) <= a(j). Given a real number x, we want to determine whether x c An, by comparing x with as few entries of An as possible. In this paper, we investigate the complexity tau (n), measured by the number of comparisons, of the above search problem. We present a 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) using an adversary argument. (c) 2006 Elsevier B.V. All rights reserved.
divisibility partially ordered set complexity search algorithm