Trans-Dichotomous Algorithms without Multiplication - some Upper and Lower Bounds

Andrej Brodnik
Peter Bro Miltersen
J. Ian Munro

May 1997

Abstract:

We show that on a RAM with addition, subtraction, bitwise Boolean operations and shifts, but no multiplication, there is a trans-dichotomous solution to the static dictionary problem using linear space and with query time tex2html_wrap_inline23. On the way, we show that two w-bit words can be multiplied in time tex2html_wrap_inline27 and that time tex2html_wrap_inline29 is necessary, and that tex2html_wrap_inline31 time is necessary and sufficient for identifying the least significant set bit of a word

Available as PostScript, PDF, DVI.

 

Last modified: 2003-06-08 by webmaster.