1 votes 1 votes Q. In Quick sort ,for sorting n element ,the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case tome complexity of the Quick sort? a) O(n) b) O(nlogn) c) O(n2) d) O(n2logn) Algorithms algorithms time-complexity + – kallu singh asked Aug 13, 2017 kallu singh 665 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes (n/4)th smallest element is selected as pivot using an O(n). n/4th smallest element will divide the array into two parts, one part will have 1/4th elements at LHS of pivot element (pivot element can be considered a part of LHS), and second part will have 3/4th elements at RHS of pivot element. As pivot element goes to its correct position every time. We'll get following recurrence relation: T(n) = T(n/4) + T(3n/4) + n Solve this recurrence relation and you will get T.C as $n*log_{4/3}^{n}$ Manu Thakur answered Aug 13, 2017 Manu Thakur comment Share Follow See all 2 Comments See all 2 2 Comments reply kallu singh commented Aug 13, 2017 reply Follow Share How to solve this type of recurrence relation.Please Explain 0 votes 0 votes Manu Thakur commented Aug 14, 2017 reply Follow Share Either use recursive tree method to solve entire recurrence relation, or for simplicity ignore the T(n/4) part and solve following recurrence relation: T(n) = T(3n/4) + n Recurrence tree for this recurrence relation will have $log_{4/3}^{n}$ levels and cost at each level is O(n). if you add the costs from each level it will come to $O(n*log_{4/3}^{n})$ for further reference: https://www.quora.com/How-do-I-find-the-time-complexity-in-T-n-T-n-4-+-T-3n-4-+-cn 0 votes 0 votes Please log in or register to add a comment.