On searching a table consistent with division poset

Publication date 26 February 2007

Abstract: 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 i n 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 i n 1, 2, ..., n

satisfying

i

divides

j

,

a_{i} < a_{j}

. Given an real number

x

, we want to determine whether

x i n A_{n}

, by comparing

x

with as few entries of

A_{n}

as possible. In this paper we investigate the complexity

a u (n)

, measured in the number of comparisons, of the above search problem. We present a

f r a c 55 n 72 + O (l n^{2} n)

search algorithm for

A_{n}

and prove a lower bound

(3 / 4 + 17 / 2160) n + O (1)

on

a u (n)

by using an adversary argument.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: On searching a table consistent with division poset