2005/05/26 by Yongxi Cheng, Xi Chen, Cheng, Yongxi +3
Computer Science · Engineering · Mathematics · #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2.1 #Mathematics and Applications #cs.DM #cs.DS #graph theory and CDMA systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.cs/0505075
16 pages, no figure; same results, representation improved, add references
openalex publication_date 2005/05/26 · arxiv created 2006/04/06 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Suppose Pn=\1,2,...,n\ is a partially ordered set with the partial order defined by divisibility, that is, for any two distinct elements i,j∈ Pn satisfying i divides j, i<Pn j. A table An=\ai|i=1,2,...,n\ of distinct real numbers is said to be consistent with Pn, provided for any two distinct elements i,j∈ \1,2,...,n\ satisfying i divides j, ai< aj. Given an 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 in the number of comparisons, of the above search problem. We present a (55n)/(72)+O(ln2 n) search algorithm for An and prove a lower bound (3/4+17/2160)n+O(1) on τ(n) by using an adversary argument.