Some Complexity Questions Related to the Query l leq k leq m Pi (Xik - X jk) : 0?
Report ID: TR-259-90Author: Ting, Hing Fung
Date: 1990-04-00
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.