# Quicksort T(n)=2T(n/2)+n

In Quicksort we devide the array in to about an half (not worst case) and we have left and right sides so it is 2T(n/2), now why in the end it is T(n)=2T(n/2)+n as we may need to go over all the array to arrange it to left and right sides?

$$T(n)$$ is number of comparisons done when quicksort sorts an array of length $$n$$.
To sort an array of length $$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$$ 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.