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

DOI10.1007/3-540-57155-8_238zbMATH Open1504.68076OpenAlexW1607877412MaRDI QIDQ5060102FDOQ5060102

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

Recommendations

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Finding repeated elements
• Time bounds for selection
• Sorting and Searching in Multisets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (7)

• Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep versus plane sweep
• Title not available (Why is that?)
• Title not available (Why is that?)
• Upper and lower I/O bounds for pebbling \(r\)-pyramids
• Algorithms – ESA 2005
• The buffer tree: A new technique for optimal I/O-algorithms
• External-memory algorithms for processing line segments in geographic information systems

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)