Question: Recall the Linear Select algorithm we learnt in the class. Suppose that we modify the algorithm to use groups of size 3 instead of 7.

Recall the Linear Select algorithm we learnt in the class. Suppose that we modify the algorithm to use groups of size 3 instead of 7. Show that the modified algorithm does not run in O(n) time. You may follow the lecture slide examples from lecture 3 when developing your recurrence equation T(n) for this version of the algorithm. That is, you can use upper bounds to get rid of the ceiling notation and assume an in-place implementation which costs nothing to separate into subsequences. (Note: For a subsequence of 3 elements, it takes at most 3 comparisons to sort them.)
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
