TY - JOUR
T1 - On the time-space tradeoff for sorting with linear queries
AU - Yao, Andrew Chi Chih
PY - 1982/8
Y1 - 1982/8
N2 - 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 TS = Ω(n2). 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}.
AB - 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 TS = Ω(n2). 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}.
UR - https://www.scopus.com/pages/publications/0041120557
U2 - 10.1016/0304-3975(82)90060-3
DO - 10.1016/0304-3975(82)90060-3
M3 - 文章
AN - SCOPUS:0041120557
SN - 0304-3975
VL - 19
SP - 203
EP - 218
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 2
ER -