4 Hash Table Load Factor (42 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 His O(n). (a) (7 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) (21 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) (7 pts) What does the claim in part (b) say about the lower bound on the runtime of searching in H in the worst case? Use big-S2 notation and justify your answer. (d) (7 pts) Combine your answers to parts (a) and (c) to conclude that the runtime for searching for a key in H is O(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