On the time-space tradeoff for sorting with linear queries |
| |
Authors: | Andrew Chi-Chih Yao |
| |
Affiliation: | Computer Science Department, Stanford University, Stanford, CA 94305, U.S.A. |
| |
Abstract: | Extending a result of Borodin et al. 1], we show that any branching program using linear queries “∑iλixi:c” to sort n numbers x1, x2,…,xn must satisfy the time-space tradeoff relation . The same relation is also shown to be true for branching programs that uses queries “min R = ?” where R is any subset of {x1, x2,…,xn}. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|