Abstract
We consider the problem of finding an element of a given rank in a totally ordered set given in a read-only array, using limited extra storage cells. We give new algorithms for various ranges of extra space. Our upper bounds improve the previously known bounds in the range of space s such that s is o(lg2 n) and s ≥ clg lg n/lg lg lg n for some constant c. We also give faster algorithms to find small ranks.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
R. J. Cole, An optimally efficient selection algorithm, Information Processing Letters 26 (6) (1988) 295–299.
G. N. Frederickson, Upper bounds for time-space trade-offs in sorting and selection, Journal of Computer and System Sciences 34 (1987) 19–26.
J. I. Munro and M. S. Paterson, Selection and sorting with limited storage, Theoretical Computer Science 12 (1980) 315–325.
J. I. Munro and V. Raman, Selection from read-only memory and sorting with minimum data movement, Theoretical Computer Science 165 (1996) 311–323.
V. Raman and S. Ramnath, “Improved Upper Bounds for Time-Space Tradeoffs for Selection with Limited Storage”, TR98/04/17, Institute of Mathematical Sciences, Chennai, India.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Raman, V., Ramnath, S. (1998). Improved upper bounds for time-space tradeoffs for selection with limited storage. In: Arnborg, S., Ivansson, L. (eds) Algorithm Theory — SWAT'98. SWAT 1998. Lecture Notes in Computer Science, vol 1432. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054361
Download citation
DOI: https://doi.org/10.1007/BFb0054361
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64682-2
Online ISBN: 978-3-540-69106-8
eBook Packages: Springer Book Archive