Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR98-028 | 28th May 1998 00:00

On Searching Sorted Lists: A Near-Optimal Lower Bound

RSS-Feed




TR98-028
Authors: Paul Beame, Faith Fich
Publication: 3rd June 1998 13:01
Downloads: 1199
Keywords: 


Abstract:


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 and Andersson's search data structure.
Thus they show sharp limitations on the running time improvements
obtainable using the unit-cost word-level RAM operations that those
algorithms employ.



ISSN 1433-8092 | Imprint