1. Consider the following algorithm, which is exactly the same algorithm we considered in the class for the Selection problem with one difference; Instead of dividing the input into groups of 5 elements, we divide the input into groups of k elements, where k is a parameter of the algorithm.

WCL_Select (A, first, last, i, k) {

if (first == last)

return A[first]; // i=1 in this case

Divide n elements into groups of k elements; //g1 g2 ... gn/k

Find the median mi each group gi;

Use WCL_Select to find the median mm of the medians of all the groups;

mid = NewPartition(A, first, last, mm); // it partitions around mm

mid_and_less = mid first + 1;

if (mid_and_less == i) // we may be lucky

return A[mid];

if (i < mid_and_less) // it is in the left subarray

return (WCL_Select(A, first, mid1, i, k));

return (WCL_Select(A, mid+1, last, i midandless, k)); }

a. Derive the recurrence for the running time of the algorithm given above. Note that the recurrence will be parametric in k as well. After you derive this recurrence, substituting k=5 in the recurrence should give the recurrence we had in the class.

b. Write the concrete recursion for k = 7. Show that running time for this recursion is still linear.

c. Find the largest odd integer value for k, for which the running time of this algorithm is superlinear (i.e. grows faster than linear). Write the concrete recursion for the value of k you suggest and show that running time is superlinear in this case.