Problem 4. (12 marks) We wish to find the median of n distinct elements (say n distinct numbers), using as few comparisons as possible. Recall that the median is an element with rank More generally, say we wish to find the k-th smallest of n elements. We could sort the n elements but this takes about n log n comparisons. Instead we do the following which, by the theorem proven in this question, uses O(n) comparisons Divide the n numbers into groups of 5 (don't worry now about what to do if n isn't divisible by 5); find the median of each group of 5, using a linear in n number of comparisons in total. This gives us about n/5 median points. Recursively find the median of these median points using about T(n/5) comparisons; call this number b. Using a linear in n number of comparisons, compare every other number to b; let Si be the set of numbers S b, and let S2 be the set of numbers > b. Because of the way b was chosen, each of Si and S2 must have at most Ton numbers. If k 4 Prove that T(n) is O(n). You should present a particular constant c and prove that T(n) S c n for all n 21 b. (6 marks) The question is why 5. What if we divide the given n numbers into groups of 3? What if we divide the given n numbers into groups of 7? In each case, give a recurrence relation and analyze its time complexity Note: Since the described median finding algorithm is famous, there are many postings in the internet about it. Perhaps one good explanation is from MIT OpenCourse Ware. Answers to the questions posted here are largely provided in some of these online documents. It is completely fine if you take ideas or approaches from such documents. But remember - you must be able to explan what you submitted