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

Let L be the set consisting of the first q positive integers. We prove 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\leq q\) can determine 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 \(\epsilon\) log log q, that is \textit{D. E. Willard}'s algorithm [Inf. Process. Lett. 17, 81-84 (1983; Zbl 0509.68106)] for finding the predecessor in O(log log q) time is optimal up to a constant factor.