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 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 ryan sequeira commented Jan 27, 2016 reply Follow Share Even in case of n/2, still satisfies the condition; contains at least 1/5th condition;and 2T(n/2) + n < T(n/5) + T(4n/5) + n. So its safe to go with option B. 5 votes 5 votes annie1234 commented Jan 28, 2017 reply Follow Share @Arjun sir Why not option d is the answer . Question is saying about number of elements into sublists each of containg atleast one fifth ..... a/c to option d the stack space will be logn base 2 which is lesser than stqck space of option b . In option b stack space will be logn base 5/4 which is greater than logn base 2 . Please correct me if i am wrong . Thanks 0 votes 0 votes Brij Mohan Gupta commented Sep 27, 2017 reply Follow Share Because we always take close answer 0 votes 0 votes Venkat Sai commented Nov 3, 2017 reply Follow Share @Arjun sir here option B is exactly equal to the required answer we dont need an approximation right ?? if we take approximation even C will be right as if we increase the number of elements the time complexity will increase and time of our required algorithm will be less than that 1 votes 1 votes MiNiPanda commented Oct 9, 2018 reply Follow Share The answer doesn't explain the "atleast" one fifth part.. :( 1 votes 1 votes goxul commented Oct 29, 2018 reply Follow Share There is an explanation for the $n$ part too - we know that quicksort takes linear amount of time to partition. Hence, the $n$ term. 0 votes 0 votes 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.