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

DOI10.1007/3-540-57155-8_238zbMath1504.68076OpenAlexW1607877412MaRDI QIDQ5060102

Mikael Bergholz Knudsen, Lars Arge, 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

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

Related Items (3)

The buffer tree: A new technique for optimal I/O-algorithms ⋮ Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep versus plane sweep ⋮ External-memory algorithms for processing line segments in geographic information systems

Cites Work

• Finding repeated elements
• Time bounds for selection
• Sorting and Searching in Multisets
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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