A general lower bound on the I/O-complexity of comparison-based algorithms

DOI10.1007/3-540-57155-8_238MaRDI QIDQ5060102zbMATH OpenOpenAlexFDO

Authors Lars Arge, Mikael Bergholz Knudsen, Kirsten Larsen

Publication date 18 January 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-57155-8_238

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05)

Recommendations

• scientific article; zbMATH DE number 4020488
• scientific article; zbMATH DE number 1305462
• Publication:4490352
• Algorithms – ESA 2005
• scientific article; zbMATH DE number 1617279

Cites work

• scientific article; zbMATH DE number 4020488 (Why is no real title available?)
• scientific article; zbMATH DE number 176491 (Why is no real title available?)
• scientific article; zbMATH DE number 177571 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• Finding repeated elements
• Sorting and Searching in Multisets
• Time bounds for selection

Cited in

(7)

• Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep versus plane sweep
• The buffer tree: A new technique for optimal I/O-algorithms
• Algorithms – ESA 2005
• External-memory algorithms for processing line segments in geographic information systems
• scientific article; zbMATH DE number 5182609 (Why is no real title available?)
• scientific article; zbMATH DE number 4020488 (Why is no real title available?)
• Upper and lower I/O bounds for pebbling \(r\)-pyramids

This page was built for publication: A general lower bound on the I/O-complexity of comparison-based algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5060102)