In Deterministic Selection the input elements are divided into a group of 5 . What will be the running time of the algorithm if we divide the input elements into a group of 7 ? What about if the input elements are divided into a group of 3 ?
When we divide the input elements into sublists of 7 elements, instead of 5 , half of the sublists has atleast 4 elements greater than the pivot. We can ignore the sublist containing the pivot and the last one that can contain at most \( 7 \) elements. Thus, the number of elements greater than pivot = \( 4(\left\lceil \frac{1}{2} \times \left\lceil \frac{n}{7}\right\rceil\right\rceil)-2 \geq (\frac{2n}{7}-8) \). |