Published on *Computer Science Department at Princeton University* (https://www.cs.princeton.edu)

Report ID:

TR-392-92

Authors:

Ting, Hing Fung [1]

Date:

December 1992

Pages:

52

Download Formats:

[Postscript [2]]

The computational complexity of sorting type problems using pairwise

comparisons has been studied extensively. For example, let $W_k ( n

)$ denote the number of pairwise comparisons needed to find the $k$

largests among $n$ distinct real numbers. It is known that $W_1 ( n )

= n - 1$, $W_2 ( n ) = n - 2 + lceil log n

ceil$ and, for fixed

$k$, $W_k ( n ) = n + ( k - 1 ) lceil log n

ceil + O ( 1 )$. In

this thesis, we study the computational complexity for selection

problems when some more powerful type of queries, namely, the queries

``$xprod:0$' are allowed. We call queries of the type

``$xprod:0$' partiy-like tests. In some problems, using parity-like

tests can significantly reduced the number of queries needed to be

asked to find an answer. For example, $ heta ( n log n )$ queries

are necessary to determine whether $n$ real numbers are distinct if

the queries are restricted to pairwise comparisons. On the other

hand, one query ``$prod_{i

ot= j} (x_i - x_j ) > 0 ?$' is

sufficient to solve the problem. In the thesis, we study the problem

of selecting the $k$ largests of $n$ distinct real numbers. We show

that when queries are restricted to parity-like tests, $n-k+lceil

log((n(n-1)...(n-k+2))

ceil$ queries are necessary to solve the

problem. In other words, the parity-like tests are not much more

powerful than the simple pairwise comparisons in this problem. We

also study the problem of finding the maximum of $n$ numbers using

small number of queries. The result on selecting the $k$ largests

implies $n-1$ parity-like tests are necessary to find the maximum of

$n$ numbers. However, we show that for any fixed $varepsilon>0$,

there is a decision tree algorithm which finds the maximum of $n$

numbers with error probability $

**Links**

[1] https://www.cs.princeton.edu/research/techreps/author/217

[2] ftp://ftp.cs.princeton.edu/techreports/1992/392.ps.gz