Q. What do you mean by the best case complexity of quick sort and outline why it is so. How would its worst case behaviour arise?
Ans:
In the best case complexity, pivot is in the middle. To simplify the calculation, we assume that the two sub-files are both exactly half of the size of the original file, and although this gives a minor overestimate, this is except able because we are only interested in a Big-Oh answer.
T(n) = 2T(n/2) + cn
which yields
T(n) = cn log n + n = O(n log n)
In the worst case the pivot is the smallest element, all the time. Then i = 0 and if we ignore T(0) = 1, which is not important, the recurrence is T(n) = T(n - 1) + cn, n > 1 which yields