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⊆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. Näher, H. Alt, A lower bound on the complexity of the union-split-find problem, SIAM J. Comput. 17 (6) (1988) 1093–1102] showed an amortized lower bound of Ω(loglogn) 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.