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.1k 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.