QUICK SORT- SELF DOUBT

Question

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)

Comments

@Verma Ashish

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

@ajaysoni1924

please post the given solution.

---

If a list contain only 10 element, then how can it be sorted, with this algo??

---

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)

Answer 1

n^3 is true but any one can explain it.

Answer 2

Option (2): O(n^2)

The time complexity in worst case for quick sort is O(n^2)

Answer 3

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