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.4k views answer comment Share Follow See all 18 Comments See all 18 18 Comments reply Aspi R Osa commented Jan 13, 2016 reply Follow Share Each of which. means? 0 votes 0 votes Tesla! commented Mar 29, 2017 reply Follow Share C can be answer you are right but B gives more accurate analysis then C 0 votes 0 votes Heisenberg commented Mar 29, 2017 reply Follow Share True . @fzx 0 votes 0 votes rfzahid commented Nov 5, 2017 i edited by Krithiga2101 Jul 20, 2019 reply Follow Share If one of the list expands ( > n/5), then the other one shrinks ( < 4n/5) which results in more balanced tree. So T(n) is less in this case. Here the worst case is when one of the list is of size exactly n/5 & the other exactly 4n/5 resulting in skewed tree. So comparatively T(n) is maximum in this case. So overall T(n) ≤ T(n/5) + T(4n/5) + n 15 votes 15 votes Magma commented Sep 21, 2018 reply Follow Share C. T(n)<=2T(4n/5)+n 0 votes 0 votes Vaishnavi01 commented Sep 21, 2018 reply Follow Share @Magma can u please explain. 0 votes 0 votes Bhagyashree Mukherje commented Sep 21, 2018 reply Follow Share https://gateoverflow.in/455/gate2008-43 0 votes 0 votes Magma commented Sep 21, 2018 reply Follow Share why option C is not correct ?? T(n) = T(n/5) + T(4n/5) + O(n) T(n) <= 2*T(4n/5) + O(n) right ?? 0 votes 0 votes Bhagyashree Mukherje commented Sep 21, 2018 reply Follow Share Option C would have been correct incase option B was missing.But since we have a more appropriate choice among the options, its B 1 votes 1 votes Magma commented Sep 21, 2018 reply Follow Share In my opinion in that case inequality shouldn't be there in Option B it should be T(n) = T(n/5) + T(4n/5) + O(n) only 0 votes 0 votes Magma commented Sep 21, 2018 reply Follow Share I may be wrong also 0 votes 0 votes Bhagyashree Mukherje commented Sep 21, 2018 reply Follow Share @magma, I think T(n) will be less than the given expression in case it is not divided in the ratio of 1/5 and 4/5 because it is atleast 1/5.Like eg,if we take the partition as 2/5 and 3/5 then The(n) will be less.Please correct me if I am wrong 1 votes 1 votes abhi19961 commented Sep 21, 2018 reply Follow Share Ans is B. 0 votes 0 votes Sandy Sharma commented Sep 21, 2018 reply Follow Share In T(n) = T(n/5) + T(4n/5) + O(n) n is taken in the worst case. Its possible to be computed in less than n swaps of quick sort. So <= inequality is necessay. 1 votes 1 votes Magma commented Sep 21, 2018 reply Follow Share Bhagyashree Mukherje Sandy Sharma thanks 1 votes 1 votes 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.