Technical Reports


Display by Author:
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Search by for:

TR-259-90
Some Complexity Questions Related to the Query l leq k leq m Pi (Xik - X jk) : 0?
Authors: Ting, Hing Fung
Date:April 1990
Pages:13
Download Formats: [PDF]
Abstract:
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.