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.
@MiNiPanda @Mk Utkarsh
"I tried the same , why masters method" failed here ?
@Sachin Mittal 1
Why master's theorem is not working here??
why here we assumed that it always be divided in t/4 and 3t/4 as pivot can be anywhwere not neccesaary to be at t/4 th position. @Gate Keeda @Debashish Deka @MiNiPanda @srestha pls explain ?
as n/4th element smallest element can be at leftmost or rightmost position also. they asked for n/4th smallest element not n/4th position.
@Sachin can you please elaborate how you got bigO(nlogn) through your recurrence relation , because we can't apply master theorem here due to different sizes of sub problems ,I'm confused so please explain ,thank you !
^ What @Sachin Mittal 1 and @dd are saying is that if $T(n) = T(\frac{n}{4}) + T(\frac{3n}{4}) + O(n)$, we can also write -:
$T(\frac{n}{4}) + T(\frac{n}{4}) + O(n) \leq T(\frac{n}{4}) + T(\frac{3n}{4}) + O(n) \leq T(\frac{3n}{4}) + T(\frac{3n}{4}) + O(n)$, or
$T(\frac{n}{4}) + T(\frac{n}{4}) + O(n) \leq T(n) \leq T(\frac{3n}{4}) + T(\frac{3n}{4}) + O(n)$
This gives us both our upper and lower bounds on $T(n)$, which we can now find by using the master theorem independently on the LHS and RHS. It's genius.
Here, The correct ans is O ( n log_{4/3}(n))
option b
Hope this helps:)
Note:
$4^{th}$ smallest will go to $4^{th}$ place.
$7^{th}$ smallest will go to $7^{th}$ place.
$\dfrac{n}{4}^{th}$ smallest will go to $\dfrac{n}{4}^{th}$ place.
$\underbrace{\left | \dfrac{n}{4}-1 \right | \fbox{$\dfrac{n}{4}^{th}$}}$ $\left | n-\dfrac{n}{4} \right |$
$\dfrac{n}{4}\ elements$
$\underbrace{O(n)}$
$\dfrac{n}{4}^{th}$
smallest element
$+$
$\underbrace{O(1)}$
Swap with
last element
partition
algo
$T\left(\dfrac{n}{4}-1\right)+T\left(n-\dfrac{n}{4}\right)$
$T(n)=O(n)+O(1)+O(n)+ T\left(\dfrac{n}{4}\right)+T\left(\dfrac{3n}{4}\right)$
$T(n)=O(n)+ T\left(\dfrac{n}{4}\right)+T\left(\dfrac{3n}{4}\right)$
$T(n)=O(n\ logn)$