Answered You can hire a professional tutor to get the answer.
Recall the (worst-case) linear-time divide-and-conquer algorithm for finding the kth smallest of n reals, where we used groups of size 5.
Recall the (worst-case) linear-time divide-and-conquer algorithm for finding the kth smallest of n reals, where we used groups of size 5. Suppose that we use the same algorithm but with groups of size g for some positive integer constant g. Derive the recurrence relation for this algorithm as a function of n and g. (Consider separately the case where g is even and where it is odd.) Based on your recurrences, determine the smallest integer g for which the algorithm runs in linear time and justify your answer. You may ignore floors and ceilings in your derivation and you do not have to write the algorithm itself.
