0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.