6.897: Advanced Data Structures Spring 2005

In this lecture, we discuss lower bounds on the cell-probe complexity of the static predecessor problem. The parameters of interest are w, the size of the machine word, and also the size of input integers, and n, the set size. Observe that a requirement on space is essential for static lower bound, since with space 2 w one can precompute all answers, and respond in constant time. In this lecture, we concentrat on bounds that are purely in w or n, and we assume the space is nO(1). In particular, we use a technique called round elimination to show that for all w there exists an n lg w such that the problem requires Ω ( lg lg w) time, and for all n there exists a w requiring Ω( time. In the next lecture, we will discuss the tradeoff between w, n, and space