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(n2)
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(n2) irrespective of the selection of the pivot element?