When we discussed the Median-of-Medians Algorithm in class, we stopped the recursion when the array-length is less-than-or-equal-to 5; when this condition was true, we just used a sort-and-pick method to pick the appropriate k-th smallest element. If T5(n) is the running-time for this version of the Median-of-Medians algorithm for an array-size of n, we get the recursion Ts(n) csn + Ts (3) +Ts (10) = Ts(n) = 100sn (1) We will consider versions of this algorithm where we stop the recursion when the array- length is less-than-or-equal-to some m (i.e. m is odd, and m # 5), and we are interested in figuring out what Tm(n) would be for different values of m. In fact, Tm(n) = acmn, for an appropriate a and Cm. This homework is about the nitty-gritty details of this process. 1. (50 points) Show that for any odd m > 5, the running-time of the Median-of- Medians algorithm will be 4m Tm(n) = - -X Cm Xn m - 3 When we discussed the Median-of-Medians Algorithm in class, we stopped the recursion when the array-length is less-than-or-equal-to 5; when this condition was true, we just used a sort-and-pick method to pick the appropriate k-th smallest element. If T5(n) is the running-time for this version of the Median-of-Medians algorithm for an array-size of n, we get the recursion Ts(n) csn + Ts (3) +Ts (10) = Ts(n) = 100sn (1) We will consider versions of this algorithm where we stop the recursion when the array- length is less-than-or-equal-to some m (i.e. m is odd, and m # 5), and we are interested in figuring out what Tm(n) would be for different values of m. In fact, Tm(n) = acmn, for an appropriate a and Cm. This homework is about the nitty-gritty details of this process. 1. (50 points) Show that for any odd m > 5, the running-time of the Median-of- Medians algorithm will be 4m Tm(n) = - -X Cm Xn m - 3