• Posted: 7 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.