A note on predecessor searching in the pointer machine model

摘要

Predecessor searching is a fundamental data structuring problem and at the core of countless algorithms: given a totally ordered universe U with n elements, maintain a subset S is contained in U such that for each element x ∈ U its predecessor in S can be found efficiently. During the last thirty years the problem has been studied extensively and optimal algorithms in many classical models of computation are known. In 1988, Mehlhorn et al. [K. Mehlhorn, S. Naeher. H. Alt. A lower hound on the complexity of the union-split-find problem, SIAM J. Cornput. 17 (6) (1988) 1093-1102] showed an amortized lower bound of Ω(log log n) in the pointer machine model. We give a different proof for this bound which sheds new light on the question of how much power the adversary actually needs.