Divide and conquer

Question

In quick sort, n numbers the (n/10)th element is selected as pivot using n^2 sortimng time complexity what will be the time complexity of quick sort is.....

a)O(nlogn)

b)O(n^2)

c)O(n^3)

d)O(n)

Comments

a

 

Answer 1

In quick sort, $\frac{n}{10}$ element is chosen as pivot using an algorithm which take time as $n^{2}$.

In worst case the $\frac{n}{10}$ element is either smallest or larget element in the input, then in 

that case it will get placed at exteme end.

Then, 

$T(n) = T(n-1) + n + n^{2}$ 

(Here, n is for PARTITION algorithm and $n^{2}$ is for the algorithm used for selection of pivot element)

As $n^{2}$ > $n$, then we can neglect it.

So,  $T(n) = T(n-1) + n^{2}$

By substitution, we get,

$T(n) = 1^{2} + 2^{2} +3^{2} + - - - - - - + (n-1)^{2} + n^{2}$

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

T(n) = O($n^{3}$)

 

Hence, Option C is Correct Answer.

---

NOTE : Here, we have to be careful because question is saying $\frac{n}{10}$ element is chosen as pivot.

If question says $\frac{n}{10}$ smallest or $\frac{n}{10}$ largest element is chosen as pivot then our equation

will change to T(n) = $T(\frac{n}{10}) + T(\frac{9n}{10}) + n + n^{2}$

Comments

but why have you assume that n/10 element is either smallest or largest. Is it because if question does ask for any specific bound then assume it to be worst case or upper bound.

---

@soyank yes, have a look at the options, they are also

asking in terms of the upper bound.