On the time-space tradeoff for sorting with linear queries

Andrew Chi Chih Yao

doi:10.1016/0304-3975(82)90060-3

On the time-space tradeoff for sorting with linear queries

Andrew Chi Chih Yao

Faculty of Electronic and Information Engineering

Research output: Contribution to journal › Article › peer-review

6 Scopus citations

Abstract

Extending a result of Borodin et al. [1], we show that any branching program using linear queries "∑_iλ_ix_i:c" to sort n numbers x₁, x₂,...,x_n must satisfy the time-space tradeoff relation TS = Ω(n²). The same relation is also shown to be true for branching programs that uses queries "min R = ?" where R is any subset of {x₁, x₂,...,x_n}.

Original language	English
Pages (from-to)	203-218
Number of pages	16
Journal	Theoretical Computer Science
Volume	19
Issue number	2
DOIs	https://doi.org/10.1016/0304-3975(82)90060-3
State	Published - Aug 1982

Access to Document

10.1016/0304-3975(82)90060-3

Cite this

@article{bfff3aae611442d68c5d5eb0c6ba41bf,

title = "On the time-space tradeoff for sorting with linear queries",

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 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\}.",

author = "Yao, \{Andrew Chi Chih\}",

year = "1982",

month = aug,

doi = "10.1016/0304-3975(82)90060-3",

language = "英语",

volume = "19",

pages = "203--218",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "2",

}

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 -

On the time-space tradeoff for sorting with linear queries

Abstract

Access to Document

Other files and links

Cite this