About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Combinatorica
Paper
A lower bound for finding predecessors in Yao's cell probe model
Abstract
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ó.