Running time analysis of a quick sort algorithm

Question

I'm reading CLRS and also watching Stanford university Algorithm courses on Coursera by Tim Roughgarden. Running time analysis of the algorithm is based on the probability that two entries in the array will ever be compared. It is not very easy to comprehend so I tried to approach the analysis in a little bit other way but I am not sure if it is correct.

Basically I try to calculate the expected pivot index returned every time partition subroutine is called.

Let pivot be expected pivot index returned every time the partition subroutine is called.

Which shows that we can expect that partition subroutine will split the subarray equally. With recursion tree illustration it would be simple to show that the depth of the tree will be log(n) and at each level of the tree it takes O(n) to partition the subarrays. Is this correct?

Answer 1

Your calculation is correct, but the interpretation isn't.

The average value of the pivot's index doesn't affect the performance analysis directly.

Imagine a very bad choice of a pivot: it chooses either the first or the last index, with probability 1/2. In this case:

pivot = 1 * 1/2 + n * 1/2 = (n + 1) / 2 ≈ n / 2

However, this is clearly the worst strategy to choose a pivot - it will lead to quadratic behavior.

What you need is a direct calculation of the running time of your algorithm. It's going to be more complicated than just a function of pivot's index (I guess, too complicated to be practical).

A more workable idea is to ask yourself a question like that:

Clearly, pivot's index is not going to be exactly n/2 all the time. However, it will almost always be close to that. How far will it be? Or, more formally, what is the probability for the pivot's index to be more than e.g. n/4 from the ideal value? And if this probability is low enough, can we limit the average depth of the tree to O(log n)? (I think yes)