4 Hash Table Load Factor (30 pts) 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 (n). (a) (5 pts) 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) (15 pts) 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 find a contradiction.) (c) (5 pts) What does the claim in part (b) say about the lower bound on the runtime of searching in H (d) (5 pts) Combine your answers to parts (a) and (c) to conclude that the runtime for searching for a key in H is (n) in the worst case. How does it compare to searching for an item in a red-black tree, which contains n items from the universe U ? 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