2

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.

NewForOlly
  • 35
  • 5
  • Does this answer your question? [Hash table runtime complexity (insert, search and delete)](https://stackoverflow.com/questions/9214353/hash-table-runtime-complexity-insert-search-and-delete) – DV82XL Jan 16 '21 at 19:23
  • Depends on what you do. Inserting `n` elements, of course requires `O(n)` operations. But then retrieving a single element is in `O(1)` because you only need a single hash operation. The length of the key is irrelevant with respect to complexity classes. – derpirscher Jan 16 '21 at 19:25
  • 1
    @derpirscher I must be understanding it incorrectly. When inserting one element, the hash method uses a loop to update the hash value for each character in the key. The loop runs as many times as there are characters in the key, so surely the hash method runs O(n) times even if it is a single hash operation. What am I missing here? – NewForOlly Jan 16 '21 at 20:03
  • 1
    First of all `n` is the number of elements in the map and has nothing to do with the size of the key. Second, O(n) notation is a theoretical construct. What's important here is the number of comparisons or hash operations. Hashing a key is counted as a single operation, regardless of the size of the key. – derpirscher Jan 16 '21 at 20:08
  • @derpirscher So a call to another method is always counted as one step, regardless of that methods time complexity? – NewForOlly Jan 16 '21 at 20:17
  • If its time complexity does not depend on the number of elements in the map, then yes, it's only one step. Hashing a single key always takes the same time, regardless of whether there are 5 elements in the map or 5 million. – derpirscher Jan 16 '21 at 20:29
  • Two different *n*s: computing a hash is linear in the number of bits in the key, but *constant* in the number of keys in the table. – chepner Jan 16 '21 at 23:30

1 Answers1

1

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.

Mo B.
  • 5,307
  • 3
  • 25
  • 42