made easy adv 2018

Question

The median of n elements can be found in  O(logn) time.which one of the following is correct about worst case time complexity of quick sort,if always median is selected as pivot element?

a)O(logn)

b)O(n)

c)O(nlogn)

d)O(nloglogn)

Comments

It should be C

---

but why

eqn should be this  right?

$T(n)=2T(\frac{n}{2})+logn$

which would give me $\Theta(n)$ on applying master theorem

---

U will have to apply partitioning algorithm which takes O(n) time after finding median...

---

@akash.dinkar12

Input is already sorted

and midium element is pivot

So, will not worst case will be one run of for loop on the input?

So, why not A)?

 

---

@srestha how can u say that input is already sorted ?

Answer 1

Since the time complexity of finding the median is O ( log n), it indicate the elements are sorted and binary search for finding the median has been applied.

Since the worst case of time complexity for taking pivot element as median the time complexity will ne O ( n log n)