On Searching Sorted Lists: A Near-Optimal Lower Bound
Paul W. Beame, Faith Ellen Fich · 1998
We obtain improved lower bounds for a class of static and dynamic data structure problems that includes several problems of searching sorted lists as special cases. These lower bounds nearly match the upper bounds given by recent striking improvements in searching algorithms given by Fredman and Willard's fusion trees [9] and Andersson's search data structure [5]. Thus they show sharp limitations on the running time improvements obtainable using the unit-cost word-level RAM operations that those algorithms employ. 1 Introduction Traditional analysis of problems such as sorting and searching is often schizophrenic in dealing with the operations one is permitted to perform on the input data. In one view, the elements being sorted are seen as abstract objects which may only be compared. In the other view, one is able to perform certain word-level operations, such as indirect addressing using the elements themselves, in algorithms like bucket and radix sorting. Traditionally, the second v...