Improved upper bounds for time-space trade-offs for selection
Venkatesh Raman, Sarnath Ramnath · Nordic journal of computing · 1999
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 ≥ (1 + e) lg lg n/ lg lg lg n for any positive constant e < 1. We also give faster rank sensitive algorithms. These algorithms are quite efficient for finding small ranks and their runtime match the upper bound of the best known algorithms when median element is to be found.