If you do not know the answer to these questions please do not comment! TY

Question 3: Median of Median Selection. In the class, we analyzed an approach for pivot selection that used median of 5 medians. Here we explore what happens with median of 3 medians. 1. Divide the input array a of size n into groups of 3 elements each. 2. Calculate the median of each group of 3 to create a new array of these medians. 3. Recursively apply the algorithm to find the median of . Let it be m. 4. Use m as the pivot element to partition the original array a. 3(a) How many elements in the array a are guaranteed to be less than the chosen pivot m? How many are guaranteed to be greater? Assume all elements in the array a are distinct. YOUR ANSWER HERE 3(b) if m computed using the median of 3 medians were used to partition the array a for a quickselect algorithm that is used to find the median of an array a, write down the recurrence for T(n), the time taken to find the median of an array of size n using the quick select algorithm with the median of 3 medians trick YOUR ANSWER HERE 3(c) The celebrated "Akra-Bazzi" method shows that the recurrence S(n) = S(an) + S((1 - a)n) + (n) with base case S(I) = @(1) has solution S(n) = (n log(n)). Use this to show that median of 3 medians trick fails to achieve a linear time algorithm for quickselect. (Note However, as we saw in the lecture, median of 5 medians works to provide (n) deterministic selection algorithm or (n log(n)) quicksort that does not depend on randomization in any way). YOUR ANSWER HERE Question 3: Median of Median Selection. In the class, we analyzed an approach for pivot selection that used median of 5 medians. Here we explore what happens with median of 3 medians. 1. Divide the input array a of size n into groups of 3 elements each. 2. Calculate the median of each group of 3 to create a new array of these medians. 3. Recursively apply the algorithm to find the median of . Let it be m. 4. Use m as the pivot element to partition the original array a. 3(a) How many elements in the array a are guaranteed to be less than the chosen pivot m? How many are guaranteed to be greater? Assume all elements in the array a are distinct. YOUR ANSWER HERE 3(b) if m computed using the median of 3 medians were used to partition the array a for a quickselect algorithm that is used to find the median of an array a, write down the recurrence for T(n), the time taken to find the median of an array of size n using the quick select algorithm with the median of 3 medians trick YOUR ANSWER HERE 3(c) The celebrated "Akra-Bazzi" method shows that the recurrence S(n) = S(an) + S((1 - a)n) + (n) with base case S(I) = @(1) has solution S(n) = (n log(n)). Use this to show that median of 3 medians trick fails to achieve a linear time algorithm for quickselect. (Note However, as we saw in the lecture, median of 5 medians works to provide (n) deterministic selection algorithm or (n log(n)) quicksort that does not depend on randomization in any way). YOUR ANSWER HERE