Question

We know that well designed closed hash tables provide efficient lookup. For half-full hash table, state the best, average and worst-case performance for search in the hash table. Explain briefly

Answer 1

Solution:

Best case:

Well, the best case will be when the element is found at the first search, this means that the best-case scenario will give us O(1) time result.

Worst case:

Worst case will be where the search query is fired each time at other half of the table which is empty, which makes the element to be found at Table size/2th times, so if the size of the tabel is M then worst case will give us O(M) time result.

Average case:

Average case will give us O(M/2) result.

Hit the thumbs up if you liked the answer. :)