On Searching a Table Consistent with Division Poset
| dc.creator | Cheng, Yongxi | |
| dc.creator | Chen, Xi | |
| dc.creator | Yin, Yiqun Lisa | |
| dc.date | 2005-05-26 | |
| dc.date | 2006-04-06 | |
| dc.date.accessioned | 2026-07-07T06:38:09Z | |
| dc.date.available | 2026-07-07T06:38:09Z | |
| dc.description | 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 $τ(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 $τ(n)$ by using an adversary argument. | |
| dc.description | 16 pages, no figure; same results, representation improved, add references | |
| dc.identifier | https://arxiv.org/abs/cs/0505075 | |
| dc.identifier | http://arxiv.org/abs/cs/0505075 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/100635 | |
| dc.subject | Discrete Mathematics | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | G.2.1; F.2.2 | |
| dc.title | On Searching a Table Consistent with Division Poset | |
| dc.type | text |