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 Wisn to nnd Che K-tn Smiallest Ol TZ elelmentS. VVe could sort Uhue Tt elernents but Unis takes abou 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 S be the set of numbers b. Because of the way b was chosen, each of S1 and S2 must have at most Ton numbers. If k S', then recursively find the k-th smallest number of Si otherwise recursively find the (k -IS)th smallest number of S2; this takes at most T(1O) comparisons a. (6 marks) Consider the following recurrence for a function T that takes on nonnegative values and is defined on integers 2 1: Prove that T(n) is O(n). You should present a particular constant c and prove that T(n) c n for all 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