BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-79-764
       ENTRY:: June 19, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: On the time-space tradeoff for sorting with linear queries
        TYPE:: Technical Report
      AUTHOR:: Yao, Andrew Chi-Chih
        DATE:: August 1979
       PAGES:: 36
    ABSTRACT:: Extending a result of Borodin, et al., we show that any
               branching program using linear queries " $\sum_{i}
               {\lambda}_i {x_i}: c$ " to sort n numbers
               $x_1$,$x_2$,...,$x_n$ must satisfy the time-space tradeoff
               relation TS = $\Omega (n_2)$. The same relation is also shown
               to be true for branching programs that use queries " min R =
               ? " where R is any subset of {$x_1$,$x_2$,...,$x_n$}.
       NOTES:: [Adminitrivia V1/Prg/19950619]
         END:: STAN//CS-TR-79-764