46 votes 46 votes Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let $T(n)$ be the number of comparisons required to sort $n$ elements. Then $T(n) \leq 2T(n/5) + n$ $T(n) \leq T(n/5) + T(4n/5) + n$ $T(n) \leq 2T(4n/5) + n$ $T(n) \leq 2T(n/2) + n$ Algorithms gatecse-2008 algorithms sorting easy + – Kathleen asked Sep 12, 2014 • edited Nov 14, 2017 by kenzou Kathleen 16.3k views answer comment Share Follow See all 18 Comments See all 18 18 Comments reply Show 15 previous comments arya_stark commented Sep 22, 2018 reply Follow Share This procedure splits the list in 1:4, so recurrence eq. should be T(n)<=T(n/5)+T(4n/5)+n Solve this we get O(nlogn). 0 votes 0 votes register_user_19 commented Oct 29, 2019 reply Follow Share Worst case:- if $i^{th}$ smallest or greatest is chosen $O(n^{2})$ (here i is constant eg. 5th largest is chosen as pivot) Best case:- if $n/4$ th smallest or largest $O(nlogn)$ 0 votes 0 votes register_user_19 commented Oct 29, 2019 i edited by register_user_19 Oct 29, 2019 reply Follow Share if we chose pivot such that it divide array in $l:m $ ratio then, $T(n) \leq T(\frac{ln}{l+m}) +T(\frac{mn}{l+m}) + \Theta (n)$ NOTE:- worst case in simple quick sort is O(n^2), we can improve this, by selection algorithm (given in cormen 2nd edition pg 189 read this it hardly take not more than 1/2 hour) so we called randomized quicksort. worst case O(nlogn) 2 votes 2 votes Please log in or register to add a comment.
Best answer 46 votes 46 votes $T(n) \leq T(n/5) + T(4n/5) + n$ One part contains $n/5$ elements and the other part contains $4n/5$ elements $+n$ is common to all options, so we need not to worry about it. Hence, the answer is option B. amarVashishth answered Nov 6, 2015 • edited Jun 20, 2021 by Lakshman Bhaiya amarVashishth comment Share Follow See all 9 Comments See all 9 9 Comments reply Show 6 previous comments HeadShot commented Nov 27, 2018 reply Follow Share @MiNiPanda hey, even though we go for more than "1/5" we will approach to better performance of quick sort. And anyhow at extreme we have to satisfy at least 1/5 , so i guess this recurrence relation will give an upper bound on QS. Please correct me if something wrong. 0 votes 0 votes Aayush Tripathi commented Aug 25, 2019 reply Follow Share worst case is T(n/5)+T(4n/5)+n because this is mentioned in the question "at least one-fifth of the elements" and the worst split is n/5 and 4n/5. Because of this A and D are not the answers because in A worst case is 2T(n/5)+n which is less than T(n/5)+T(4n/5)+n similarly D can't be the answer. C cannot be the answer because the equality never holds. Hope this helps. 2 votes 2 votes shashankrustagi commented Jan 16, 2021 reply Follow Share It is directly from CORMEN 0 votes 0 votes Please log in or register to add a comment.
12 votes 12 votes The answer is B. With 1/5 elements on one side giving T(n/5) and 4n/5 on the other side, giving T(4n/5). and n is the pivot selection time. Gate Keeda answered Dec 11, 2014 Gate Keeda comment Share Follow See all 2 Comments See all 2 2 Comments reply _xor_ commented Jun 5, 2015 reply Follow Share n is partition time . i think so . is it ??? 7 votes 7 votes Sandeep Suri commented Jan 13, 2017 reply Follow Share Yes @xor 1 votes 1 votes Please log in or register to add a comment.
3 votes 3 votes Those who are confused between B and C .One thing is sure,If B is correct then C is also correct. i.e,if T(n)<=T(n/5)+T(4n/5)+n; implies T(n)<2T(4n/5)+n. Hence,here We will chosse TIGHTEST-BOUND i.e. Option:B Raas Star answered Sep 17, 2019 Raas Star comment Share Follow See 1 comment See all 1 1 comment reply psych0 commented Dec 19, 2023 reply Follow Share helpful 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes If you create two list containing 1/5th elements and in other it contains rest of the elements. If you go through the pivot elements it should give you recurrence relation T(n) = T(n/5) + T(4n/5) + n So option B is correct. Parth27 answered Mar 2, 2020 Parth27 comment Share Follow See all 0 reply Please log in or register to add a comment.