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

  • Andrej Brodnik
  • Peter Bro Miltersen
  • J. Ian Munro

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 sqrt(log n(log log n)^(1+o(1))). On
the way, we show that two w-bit words can be multiplied in
time (log w)^(1+o(1)) and that time Omega(log w) is necessary, and that
Theta(log log w) time is necessary and sufficient for identifying the
least significant set bit of a word.
Published
1997-01-12
How to Cite
Brodnik, A., Miltersen, P., & Munro, J. (1997). Trans-Dichotomous Algorithms without Multiplication —some Upper and Lower Bounds. BRICS Report Series, 4(12). https://doi.org/10.7146/brics.v4i12.18803