$(11$ points$)$ Recall the $($worst$-$case$)$ linear$-$time divide$-$and$-$conquer algorithm for finding the $k$ th

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.