Self Doubt - Quick Sort

Question

Consider the following inputs:

1) 2 2 2 2 2 2 2

2) 1 2 3 4 5 6 7

3) 7 6 5 4 3 2 1

In all three cases, the worst-case time complexity of quicksort is O(n²)

 

My doubt is if I am taking the middle element as a pivot, then my recursive equation for the above three cases will become: T(n) = T(n/2) + O(n), right?

Can someone explain how we are saying worst-case time complexity for these three cases is O(n²) irrespective of the selection of the pivot element?

 

Comments

I don't think you should get worst case if you take the middle element as the pivot. What is the source of your claim?

---

it is basic question refer to theory again

---

@Gurdeep, Sir, Can you please provide a proper explanation for the above scenario

---

@garvit

dont call me sir  

have sent you a link( personal message) watch lecture 9 and 10 both yor will get everything about quick sort

---

What is the recurrence relation in case of quick sort if pivot = median of first ceil(n^1/3) elements.

Answer 1

we get best case when we select median element as pivot and not middle element. fixing any position in the array as pivot may give worst case O(n^2).that is why randomised quick sort performs better coz u don't fix pivot position.