Some Complexity Questions Related to the Query l leq k leq m Pi (Xik - X jk) : 0?
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.