$4.(10$ points$)$ Consider the following Qsort algorithm, which takes an input sequence $\backslash ($ A $\backslash )$ of elements to be sorted. In the pseudocode, $|$A $|$ denotes the number of elements of $\backslash ($ A $\backslash ),$ and $//$ denotes concatenation. Assume that $|$ A $|$ is a power of $4$ and all elements are distinct.

Qsort $($A$)$

$1.$ if $(|$A$|$ S $3)$ sort A directly else $\backslash \{$

$2.$ find $\backslash ($ p $\backslash ),$ the $\backslash (($n $/4)^\{$t h$\}\backslash )$ smallest element of $\backslash ($ A $\backslash )$;

$3.$ split A into A$1$ and A$2$ such that

A$1\backslash (=<mtext></mtext><mi>\backslash </mi><mi>)</mi>$ all elements of $\backslash ($ A $\backslash )$ that are less than or equal to $\backslash ($ p$>\backslash )$

A$2\backslash (=<mtext></mtext><mi>\backslash </mi><mi>)</mi>$ all elements of $\backslash ($ A $\backslash )$ that are greater than $\backslash ($ p$>\backslash )$

$4.$ Return $($Qsort$($A$1)//$Qsort$($A$2))$; $\backslash \}$

Write a recurrence relation for $\backslash ($ T$($n$)\backslash )$ to describe the time complexity of Qsort, where $\backslash ($ n $\backslash )$ is the number of elements of $\backslash ($ A $\backslash ).$