Lower Bounds for Sorting with Realistic Instruction Sets
- 1 April 1985
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-34 (4) , 311-317
- https://doi.org/10.1109/tc.1985.5009381
Abstract
Ω(n log n) time is required to sort n integers using comparison, addition, subtraction, multiplication, division, indirect addressing, and mildly restricted truncation.Keywords
This publication has 6 references indexed in Scilit:
- Upper bounds for sorting integers on random access machinesTheoretical Computer Science, 1983
- Lower bounds for algebraic computation treesPublished by Association for Computing Machinery (ACM) ,1983
- On the computational power of the floor functionInformation Processing Letters, 1982
- Preserving order in a forest in less than logarithmic time and linear spaceInformation Processing Letters, 1977
- Design and implementation of an efficient priority queueTheory of Computing Systems, 1976
- Some results on the effect of arithmetics on comparison problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1972