0
$\begingroup$

What's the complexity of inserting an integer $n$ to an empty hash table? My guess is that it's $O(\log n)$ as we require to scan every bit of $n$ to compute its hash. However, I often see it as $O(1)$. Am I mixing up things here ?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

The answer depends on your model of computation. In other words, it depends on how you count the number of basic operations, or on what you consider to be a "basic operation".

In the transdichotomous model or Word RAM model, you can do computation on an entire word in $O(1)$ time, and the word size is guaranteed to be large enough to hold the integer (and, in particular, at least $\log n)$. An operation on a single word counts as a single operation, even though you're operating on a bunch of bits. Consequently, there exist hash functions that can hash the number $n$ in $O(1)$ time, in these models of computation.

In the bit complexity model, it takes at least $\log n$ time to read an integer with $\log n$ bits, so you're right that hashing $n$ will take $\Omega(\log n)$ time.

You might find it useful to read https://en.wikipedia.org/wiki/Transdichotomous_model and https://cstheory.stackexchange.com/q/2656/5038.

Ultimately, the time to compute a hash will depend on the hash function (some hashes might be even slower than the above), but this might be enough to clear up your particular question.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.