A Time-Space Tradeoff for Element Distinctness

DOI10.1137/0216007zbMath0636.68040OpenAlexW2089892120MaRDI QIDQ3776617

Avi Wigderson, Friedhelm Meyer auf der Heide, Allan Borodin, Eli Upfal, Faith E. Fich

Publication date: 1987

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0216007

zbMATH Keywords

computational complexitysortingspace lower boundstime-space tradeoffstime lower boundselement distinctness

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10)

Related Items

Time-space tradeoffs for algebraic problems on general sequential machines, Time-space tradeoffs in algebraic complexity theory, Trade-offs between communication and space, Time-space tradeoffs for set operations, Computing (and Life) Is All about Tradeoffs, Time-space tradeoffs for branching programs, Alphabet dependence in parameterized matching, Determinism versus nondeterminism for linear time RAMs with memory restrictions