### Divide the elements of an array into group of 3 or 7, instead of 5 in Deterministic Selection algorithm timecomplexity deterministicselection sorting quicksort    Posted: 5 years ago Updated: 4 years ago Edit answers (1) views (15478) Comments (1)

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 ?

 I understand the explanation just not how you know half of the sublists has at least 4? How do you figure that out for any numb - posted 8 months ago @mevansphxaz1

 Posted: 5 years ago 0 0 Edit 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)$$.For similar reason the number of elements smaller than pivot is atleast $$(\frac{2n}{7}-8)$$. The recurrence part of the algorithm works on a problem of size atmost $$n-(\frac{2n}{7}-8)=(\frac{5n}{7}+8)$$. $$\therefore$$ Running time = $$T(n)\leq T(\left\lceil\frac{n}{7}\right\rceil)+T(\frac{5n}{7}+8)+O(n)$$ .Therefore, the algorithm runs in linear time.When we are dividing the input elements as a sublist of $$3$$, we get the running time $$T(n)\leq T(\left\lceil \frac{n}{3}\right\rceil)+T(\frac{2n}{3}+4)+O(n)$$ where the subproblem size at the recurrence is atmost $$n-(\frac{n}{3}-4)=(\frac{2n}{3}+4)$$ and the number of elements smaller or greater than the pivot is $$2(\frac{1}{2} \times \left\lceil \frac{n}{3}\right\rceil-2)\geq (\frac{n}{3}-4)$$ .Therefore, the algorithm does not run in linear time.When we are dividing the input as a group of 5 or 7 elements, the total size of the problem has been reduced to less than n , whereas for the sublist of 3 elements, the size of the problem is not reduced.