Hash Table Load Factor

We want to store a set of n keys into a hash table H, that is of size m and uses chaining as the collision resolution method. In this problem you will prove that if the keys are drawn from a universe U of size |U| > nm, then regardless of what hash function we use, the worst case runtime for searching in H is Theta(n).

(a) What is the upper bound for the runtime of searching in H in the worst case? Use big-O notation and justify your answer.

(b) Prove that no matter what hash function we use, U always contains a subset of size n consisting of keys that all hash to the same slot. (Hint: assume that there is no such subset and and a contradiction.)

(c) What does the claim in part b say about the lower bound on the runtime of searching in H inthe worst case? Use big-Theta notation and justify your answer.

(d) Combine your answers to parts (a) and (c) to conclude that the runtime for searching in H is Theta(n) in the worst case. How does it compare to searching for n items from the universe U in a red-black tree? When would we want to use a hash table and when would we want to use a red-black tree as a data structure to store and search for items?