Quicksort T(n)=2T(n/2)+n
$T(n)$ is number of comparisons done when quicksort sorts an array of length&nbsp;$n$.

To sort an array of length&nbsp;$n$, we must split it into two halves and sort the halves.  To split the array, we must compare each element of the array against the pivot, which is $n$&nbsp;comparisons.  (Perhaps $n-1$ if the pivot is an actual array value rather than, say, an estimate of the median.) Then, we must recursively sort the two halves, which requires $T(n/2)$ comparisons each.