Notes on the complexity of sorting in abstract machines

DOI10.1007/BF01936140zbMath0582.68033OpenAlexW2041230269MaRDI QIDQ1068551

Jyrki Katajainen, Martti Penttonen

Publication date: 1985

Published in: BIT (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01936140

zbMATH Keywords

linear time algorithmpointer machinessuccessor-predecessor random access machines

Mathematics Subject Classification ID

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

Related Items (2)

New method in information processing for maintaining an efficient dynamic ordered set ⋮ Notes on the complexity of sorting in abstract machines

Cites Work

• A class of algorithms which require nonlinear time to maintain disjoint sets
• Upper bounds for sorting integers on random access machines
• Notes on the complexity of sorting in abstract machines
• Time bounded random access machines
• Storage Modification Machines
• Unnamed Item
• Unnamed Item

This page was built for publication: Notes on the complexity of sorting in abstract machines