class test

Question

Given an array of n numbers, a median x exists such that x is larger than at least n/20 of the numbers and smaller than at lest n/20 numbers. If this x is used as a pivot in quick sort. What is the worst case running time of this algorithm?

a. O(n)

b. O(n^11/10)

3. O(nlogn)

4.O(n²)

5. O(n^10/11 log n)

Comments

i just to find median of array i.e. n/2 element in sorted array, which will be grater than n/20 element as well as greater than.

we can use medians of median algorithm.

---

@Shubhanshu

your recurrence relation is not correct.

you are taking 2T($\frac{n}{20}$), this means in next iteration you will only deal with $\frac{n}{20}+\frac{n}{20}$ = $\frac{n}{10}$ elements..

what about other elements ??

---

Yes it is O(nlog_20/19n) which we can consider as O(nlogn) if that particular value is not given in the option.