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