0 votes 0 votes In quick sort for sorting of n Numbers, the 75th greatest Element is selected as pivot using $O(n^2)$ time complexity algorithm than what is the worst case time complexity of quick sort. O($n^2$) O($n^3$) O(nlogn) O(n) Algorithms algorithms divide-and-conquer quick-sort + – ajaysoni1924 asked Sep 2, 2019 ajaysoni1924 3.5k views answer comment Share Follow See all 12 Comments See all 12 12 Comments reply Show 9 previous comments ankitgupta.1729 commented Sep 4, 2019 reply Follow Share @Verma Ashish yeah, it seems to $O(n^3)$ but I didn't solve it. @ajaysoni1924 please post the given solution. 0 votes 0 votes srestha commented Sep 4, 2019 reply Follow Share If a list contain only 10 element, then how can it be sorted, with this algo?? 0 votes 0 votes Sanandan commented Sep 12, 2020 reply Follow Share Quick Sort in worst case takes O(n^2) time but in this case as selection algorithm takes O(n^2) time , worst case complexity is O(n^3) 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes n^3 is true but any one can explain it. Deepak saroj answered Sep 6, 2019 Deepak saroj comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Option (2): O(n^2) The time complexity in worst case for quick sort is O(n^2) Shagun Singh answered Sep 17, 2019 • edited Sep 18, 2019 by Shagun Singh Shagun Singh comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes T(n)=T(74)+T(n-75)+n²+n so, we can write as, T(n)=T(n-75)+n²+n n. Cost : n²+n n-75. (n-75)²+(n-75) n-2×75. (n-2×75)²+(n-2×75) n-3×75 . . n-75k. (n-75k) ²+(n-75k) So, T(n)=n²+(n-75)²+(n-2×75)²+........+n+(n-75)+(n-2×75)+.… =O(n²)+O(n) =O(n²) Onika answered Nov 12, 2021 Onika comment Share Follow See 1 comment See all 1 1 comment reply yashumap17 commented 10 hours ago reply Follow Share Adding n^2 , n times will give n^3 not n^2 0 votes 0 votes Please log in or register to add a comment.