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$}.

http://i.stanford.edu/pub/cstr/reports/cs/tr/79/764/CS-TR-79-764.pdf