Lower bounds for sorting of sums

DOI10.1016/0304-3975(89)90132-1zbMath0686.68034OpenAlexW2067618361MaRDI QIDQ1262763

Martin Dietzfelbinger

Publication date: 1989

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90132-1

zbMATH Keywords

sortinglower boundsalgorithmical complexity

Mathematics Subject Classification ID

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

Related Items (2)

Better lower bounds on detecting affine and spherical degeneracies ⋮ Sorting the sums \((x_ i+y_ j)\) in \(O(n^ 2)\) comparisons

Cites Work

• Unnamed Item
• Exponential lower bounds for some NP-complete problems in a restricted linear decision tree model
• Lower bound arguments with ``inaccessible numbers
• Comparisons between linear functions can help
• How good is the information theory bound in sorting?
• On the complexity of computations under varying sets of primitives
• Balancing poset extensions
• A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
• Sorting X + Y

This page was built for publication: Lower bounds for sorting of sums