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
$+$
$\underbrace{O(n)}$
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)$