# 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?

## 2 Answers

$$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.

This last term n should, more precisely, be n-1, not n. It arises out of the fact that for splitting the array into 2 parts: one part consisting of all elements smaller than pivot and another consisting of all elements greater than or equal to pivot, we have to perform exactly n-1 (comparison) operations.