4 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 (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 keys that all hash to the same slot. (Hint: assume that there is no such subset and find a contrudiction) the worst case? Use big- 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 (c) (5 pts) What does the claim in part (b) say about the lower bound on the runtime of searching in H in