In quick-sort, for sorting $n$ elements, the $\left(n/4\right)^{th}$ smallest element is selected as pivot using an $O(n)$ time algorithm. What is the worst case time complexity of the quick sort?
$\Theta(n)$
$\Theta(n \log n)$
$\Theta(n^2)$
$\Theta(n^2 \log n)$
Answer is B.
$T(n)= O(n)$ pivot selection time $ + T(n/4 - 1) + T(3n/4)$
which'll give $\Theta\left(n \log n\right)$.
Pivot selection complexity is given in questions. Pivot being the $(n/4)$th smallest element, once it is found, we have two sub arrays- one of size $(n/4 - 1)$ and other of size $(3n/4)$ and for both of these we solve recursively.
height of this recurrence tree is log_{4/3} n and cost of every level <=n
so, (n+n+-----log_{4/3 }n times) = O(n log_{4/3}n)
SO ans is B
..................
Read the question.. it is mentioned that
the (n/4)th smallest element is selected as pivot
So if it resides at its correct position then the list is divided like n/4 and 3n/4.
Here, The correct ans is O ( n log_{4/3}(n))
Gatecse