quick sort time complexity

Question

the worst case time complexity of quicksort for an elements when the median is selected as the pivot

a. o(n^2)

b.o(n)

c.o(nlogn)

d.o(logn)

Answer 1

Answer C) O(nlogn),  when median selected as pivot, partition method will divide array into equal halves.. so logn level recursion tree will form with cn work(partition method)  at each level..
The recurence would be..
T(n) = 2T(n/2) + Θ(n)
Therefore total time complexity =Θ(nlogn)  in all cases

Note:O(n) time algo available for median finding
https://en.m.wikipedia.org/wiki/Median_of_medians

Comments

same recurrence relation will be applied here also

---

if all elements are same then worst case partitioning will occur. How O(nlogn) then?

---

Here it doesn't matter all the elements are same or not because it will divide the array in two equal parts which gives the recurrence relation for best case of quick sort