|
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] |
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. |
|