33 votes 33 votes Which one of the following is the recurrence equation for the worst case time complexity of the quick sort algorithm for sorting $n\;( \geq 2)$ numbers? In the recurrence equations given in the options below, $c$ is a constant. $T(n) = 2 T (n/2) + cn$ $T(n) = T ( n - 1) + T(1) + cn$ $T(n) = 2T ( n - 1) + cn$ $T(n) = T (n/2) + cn$ Algorithms gatecse-2015-set1 algorithms recurrence-relation sorting easy + – makhdoom ghaya asked Feb 11, 2015 • edited Jun 19, 2021 by Lakshman Bhaiya makhdoom ghaya 11.5k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Raju Kalagoni commented Dec 14, 2019 reply Follow Share What does cn indicates ? 0 votes 0 votes `JEET commented Jan 2, 2020 reply Follow Share It means any constant which is multiplied to $\mathbf n$. 0 votes 0 votes Kiyoshi commented Jun 11, 2021 reply Follow Share In quick sort, one thing to notice generally we don’t take pivot in recurrence relation but here we considered the pivot as well. 0 votes 0 votes mayank_1 commented Jan 5 reply Follow Share T(n-1): Time taken to recursively sort the sub array of size (n-1) when partitioning is performed. T(1): Time taken to recursively sort the sub array of size 1 when partitioning is performed (base case). cn: The time taken for the partitioning step, where "c" is a constant representing the time taken per element during partitioning, and "n" is the size of the array being partitioned. 0 votes 0 votes Please log in or register to add a comment.
Best answer 42 votes 42 votes Correct Option: B Worst case for quick sort happens when $1$ element is on one list and $n-1$ elements on another list. Arjun answered Feb 11, 2015 • edited May 12, 2021 by soujanyareddy13 Arjun comment Share Follow See all 9 Comments See all 9 9 Comments reply Vishal Raman commented Aug 7, 2015 reply Follow Share But according to Cormen, worst case for Quicksort algo occurs when the partitioning produces one subproblem with n-1 elements and another with zero elements ( the nth element is the pivot which gets added to the end of the first subproblem). In fact, it states that even a partition with a 9:1 proportional split also runs in O(n lg n) time. 10 votes 10 votes Arjun commented Aug 7, 2015 reply Follow Share Yes. n-1 elements on one list- 0 on other list is because 'pivot' is ignored- which is anyway placed. 4 votes 4 votes Vishal Raman commented Aug 7, 2015 reply Follow Share So option B should really be T(n)=T(n-1)+T(0) +cn 7 votes 7 votes Arjun commented Aug 7, 2015 reply Follow Share Yes. But can't say the given is wrong either. 3 votes 3 votes Vishal Raman commented Aug 8, 2015 reply Follow Share Yes sir. Asymptotically they are the same. 5 votes 5 votes anchitjindal07 commented Oct 22, 2017 reply Follow Share Isn't it option D for quick sort? 0 votes 0 votes Regina Phalange commented Nov 2, 2017 reply Follow Share Option D means we are dividing the elements in half which is not the case for worst condition. 0 votes 0 votes adeebafatima1 commented Oct 26, 2018 reply Follow Share can't say the given is wrong because asymptotically they are the same.Is it? 0 votes 0 votes `JEET commented Jan 2, 2020 reply Follow Share For Worst Case correct Recurrences are: $\mathbf{T(n) = T(0) + T(n-1) + \theta (n)}$ which is the same as: $\mathbf{T(n) = T(n-1) + \theta (n)}$ The solution of this recurrence is $\mathbf{\theta (n)}$ Maybe the examiner have something to do with $\mathbf{n \ge 2}$ case. If this isn't the case, then the options are definitely wrong $\color{blue} {\text{According to Cormen and Wikipedia.}}$ 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Quick sort worst case time complexity is n^2, when the array is sorted or almost sorted then Quicksort algorithm runs in O(n^2) time. The recurrence relation for Quick sort worst case time complexity is T(n) = T(n-1) + T(1) + cn. Hence, B is Answer. manish_pal_sunny answered Aug 21, 2020 manish_pal_sunny comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes If the pivot is chosen as the last position then there is a left recursive of size (n-1) or right recursive call of size 0. 1.Partition function->O(n) 2.T(n-1) time in left recursive call 3.T(1) time in right recursive call Recurrence relation: T(n-1)+T(1)+cn Option B is correct himanshu dhawan answered Apr 9, 2021 himanshu dhawan comment Share Follow See all 0 reply Please log in or register to add a comment.