Optimal bounds for the predecessor problem
Paul W. Beame, Faith Ellen Fich · 1999
We obtain matching upper and lower bounds for the amount of time to find the predecessor of a given element among the elements of a fixed efficiently stored set.Our algorithms are for the unit-cost word-level RAM with multiplication and extend to give optimal dynamic algorithms.The lower bounds are proved in a much stronger communication game model, but they apply to the cell probe and RAM models and to both static and dynamic predecessor problems.