3,469 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)

3 Answers

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²)

Related questions