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.6k views answer comment Share Follow See all 12 Comments See all 12 12 Comments reply Verma Ashish commented Sep 2, 2019 reply Follow Share It will be O(n²). 0 votes 0 votes adarsh_1997 commented Sep 3, 2019 reply Follow Share in worst case it must be 0(n^2) 0 votes 0 votes srestha commented Sep 3, 2019 reply Follow Share @ajaysoni1924 what is ans?? I think even sorting not possible, in this case. 0 votes 0 votes ankitgupta.1729 commented Sep 3, 2019 reply Follow Share @Verma Ashish how ? 0 votes 0 votes Verma Ashish commented Sep 3, 2019 reply Follow Share What i think is- There is no need to select 75th greatest element as pivot.. because its its searching itself takes O(n²) time.. Whatever pivot is selected quick sort worst case O(n^2). 0 votes 0 votes ankitgupta.1729 commented Sep 4, 2019 i edited by ankitgupta.1729 Sep 4, 2019 reply Follow Share Whatever pivot is selected quick sort worst case O(n^2) but here it is given that this procedure takes $O(n^2)$ time and in original quick sort, it takes O(1) time because we go to that index in array and select it and then do the partition procedure. Here, I think, we have to include $O(n^2)$ in recurrence. So, recurrence will look like $T(n) = T(74) +T(n-75) + O(n^2) + O(n)$ O(n^2) to select pivot then partition will take O(n) time and after partition, 74 elements which are right of 75th greatest elements will be more than 75th greatest element and elements on left side will be less than that 75th greatest element. Now here T(74) will be constant(c) and now we have to solve recurrence to find running time. please correct me if I am wrong. 1 votes 1 votes ajaysoni1924 commented Sep 4, 2019 reply Follow Share Yes, answer is O($n^2$). But I am not getting why recurrence relation is different if 75th minimum element is selected as pivot is given. 0 votes 0 votes ajaysoni1924 commented Sep 4, 2019 reply Follow Share @sresthaHow sorting is not possible??? It is possible I think??? 0 votes 0 votes Verma Ashish commented Sep 4, 2019 i edited by Verma Ashish Sep 4, 2019 reply Follow Share @ankitgupta.1729 $T(n)=T(n-75)+T(74)+O(n^2)+O(n)$ it will lead to $O(n^3)$ right? Whatever pivot is selected quick sort worst case O(n^2). That was unconsciously written.. We can chose first or last element as pivot..$T(n)=T(n-1)+T(0)+O(n)=O(n^2)$ 0 votes 0 votes 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 5 days 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.