Lower bounds for static dictionaries on RAMs with bit operations but no multiplication
| Author(s) : | Peter Bro Miltersen, |
| Publisher : | N/A |
| Publication Date : | 1996 |
| ISSN : | N/A |
| Abstract : | Abstract. We consider solving the static dictionary problem with n keys from the universe f0; : : : ; m \Gamma 1g on a RAM with direct and indirect addressing, conditional jump, addition, bitwise Boolean operations, and arbitrary shifts (a Practical RAM). For any ffl? 0, tries yield constant query time using space m ffl, provided that n = m o(1). We show that this is essentially optimal: Any scheme with constant query time requires space m ffl for some ffl? 0, even if n (log m), |