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

Report ID:

TR-259-90

Authors:

Ting, Hing Fung [1]

Date:

March 1990

Pages:

13

Download Formats:

[PDF [2]]

In this paper, we study the computational power of the l leq k leq m Pi (Xik - Xjk):0 decision tree model which allows queries of the type l leq k leq m Pi (Xik - Sjk) : 0. We prove that, in this model, n + (k - 1)[log n] + 0(1)

queries are necessary and sucient to select the k largest of n distinct real numbers. We also prove that 2n+o(n) queries of the type l leq k leq m Pi (Xik - Xjk):0? are sufficient to select the kth largest of n numbers. On another classical issue of complexity studies, namely the time-space tradeoff of a problem, we show that our model is closely related to the binary-comparison decision tree model.

**Links**

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

[2] ftp://ftp.cs.princeton.edu/techreports/1990/259.pdf