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

can you tell the algo, which gives median in O(n) time?

---

https://en.m.wikipedia.org/wiki/Median_of_medians

---

Thanks :)

---

What if all elements are equal

---

then also O(nlogn)

---

@prashant can u explain. How it will be O(nlogn) when all elements are same

---

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