Report Number: CS-TR-79-764
Institution: Stanford University, Department of Computer Science
Title: On the time-space tradeoff for sorting with linear queries
Author: Yao, Andrew Chi-Chih
Date: August 1979
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$}.