Here is a Select Algorithm.

1: Let B[1.. n/5] be a new array of arrays 2: Let C[1.. n/5] be a new array 3: Break A into /5 groups of 5 elements, placing each

into a new array in B (the group might have less than five

elements, this is fine)

4: Sort each group of 5 elements with insertion sort, then

place the median into the corresponding position in C

5: x = SELECT(C[1...n/5],m), for =ceiling(1/2(ceiling(n/5))) Comment: x is the median of the medians in C

6: Partition A around x. Let i be the position of element x after the partitioning.

7: if i=k then

8: Return x

9: else if k

10: return SELECT(A[1..i],k)

11: else

12: return SELECT(A[i + 1..n], k i)

12: return SELECT(A[i + 1..n], k i)

Considering this Select algorithm, which determines the ith smallest element in an array of size n in O(n) time for the worst case input. The first step of this algorithm is division into n/5 groups of 5 elements each. Consider other two versions of this algorithm: the first one uses division into n/3 groups of 3 elements each and the second one uses division into n/7 groups of 7 elements each. Otherwise both algorithms implement the same routine as Select. Which algorithm is asymptotically faster, the one with division into groups of 3, groups of 5 (standard Select), or groups of 7? Prove your statement.