CODEWITHSUNDEEP
data-structureshashtable
sia
sia

Reputation: 1910

how to find the maximum and minimum time taken to search a hashtable?

I was recently asked this question on an interview:

Find the maximum and minimum time taken to search in a hash-table

I said it depends upon the load factor and hash-function but it was not a convincing answer.

Please provide your expert review about the question above.

Upvotes: 2

Views: 1165

Answers (1)

Srinivasarao Daruna
Srinivasarao Daruna

Reputation: 3374

For hashing the performance depends on how well you have handled the collision (getting same hash value for multiple inputs). But, as per the theory, Best Time complexity of hashing is O(1) and worst time complexity is O(n). Worst case can occur if all the inputs got same hash value and if you used a collision resolution technique such as linear probing. You can check the wiki link

http://en.wikipedia.org/wiki/Hash_table

Which clearly tells that worst time complexity for search is O(n). Its worth while to check all the collision resolution techniques as well once.

For finding best case, I might not be able to give complete solution but, Best case for hashing is , while inserting you insert all the values with different hash value and search, and for the worst case, you need to insert different values with same hash value and search.

Upvotes: 2

Related Questions