A lower bound for finding predecessors in Yao's cell probe model

Let L be the set consisting of the first q positive integers. We prove in this paper that there does not exist a data structure for representing an arbitrary subset A of L which uses poly (|A|) cells of memory (where each cell holds c log q bits of information) and which the predecessor in A of an arbitrary x≦q can be determined by probing only a constant (independent of q) number of cells. Actually our proof gives more: the theorem remains valid if this number is less than ε log log q, that is D. E. Willard's algorithm [2] for finding the predecessor in O(log log q) time is optimal up to a constant factor. © 1988 Akadémiai Kiadó.