time-complexitybig-o

Why is a hash table considered O(1) time complexity and not O(n)?


The underlying hashing algorithm hashes each character of the key, I understand this to be O(n) where n is the length of the key.

How can a hash table be considered O(1) when one of its underlying methods O(n)? I thought the worst-case complexity takes priority.


Solution

  • It all depends on your assumptions, and what you consider as a variable parameter in your analysis.

    Usually, when you talk about the complexity of hash table operations, you ignore the details of the hash function and (probably unrealistically) assume it to be O(1), i.e. independent of the key length, or you implicitly assume the key length to be bounded by a constant. That means that the only parameter of interest usually is the number of elements in the hash table.

    But if you want to look deeper, you are actually right that one could also consider the length of the key to be a measurable parameter of the complexity analysis. But then it really depends on the type of the keys and the details of the hash function. It may well be, as you said, that the complexity of the hash function itself is linear in the length of the key (but not necessarily). You could then specify the complexity as a function in two variables instead of just one.