Optimal bounds for the predecessor problem
| Author(s) : | Faith E. Fich Paul Beame, |
| Publisher : | N/A |
| Publication Date : | 1999 |
| ISSN : | N/A |
| Abstract : | 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. 1, |