in Algorithms
2,637 views
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.

  1. O($n^2$)
  2. O($n^3$)
  3. O(nlogn)
  4. O(n)
in Algorithms
2.6k views

4 Comments

@Verma Ashish

yeah, it seems to $O(n^3)$ but I didn't solve it.

@ajaysoni1924

please post the given solution.

0
0
If a list contain only 10 element, then how can it be sorted, with this algo??
0
0
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
0

3 Answers

0 votes
0 votes
n^3 is true but any one can explain it.
0 votes
0 votes
Option (2): O(n^2)

The time complexity in worst case for quick sort is O(n^2)
edited by
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²)
by

Related questions