\

1) Prove that the worst case running time of the BIGFIVE algorithm is O(nlgn) if we put the elements of S into groups of 3 . Assum e that n is a multiple of 3.

2) Prove that the worst case running time of the BIGFIVE algorithm is O(n) if we put the elements of S into groups of 7.

The following algorithm, called the big five algorithm, both because of the cardinality and stature of its inventors (Blum, Floyd, Pratt, Rivest, and Tarjan) and because of the importance of the number 5 in its design, returns the k-th smallest element of the input set S function BIGFIVE(S, k) Put the elements of S into groups of 5 and sort each group Let M- y y is the 3rd smallest key (median) in its group Let x BIGFIVE (M, LIMI/2 Use x as a pivot to divide S - (x into two subsets if k =-|L|, then return x else if k