# Quicksort Running Time

I am trying to refresh my knowledge (and hopefully learn more) about Algorithm Analysis. I took a course on this two years ago but I am trying to catch up on what I had learned back then.

The way I am going about it is by doing exercises from the classic text Introduction to Algorithms, 2nd Edition - CLRS.

The problem that I am trying to solve is this:

Exercise 7.2-2
What is the running time of QUICKSORT when all elements of array A have the same value?

My Solution
The running time of QUICKSORT when all elements of array A have the same value will be equivalent to the worst case running of QUICKSORT since no matter what pivot is picked, QUICKSORT will have to go through all the values in A. And since all values are the same, each recursive call will lead to unbalanced partitioning.

Thus the recurrence will be:

$$T(n) = T(n-1) + \Theta(n)$$

The above recurrence has the solution (I will prove this later):

$$T(n) = \Theta(n^2)$$

Hence the running time of QUICKSORT in this case is $$\Theta(n^2)$$

Please let me know if this question should be posted elsewhere in the SE network.

Thanks!

Jake Clawson

-
That is correct. – fdart17 Feb 18 '11 at 1:19
In the future you might want to visit cstheory.stackexchange.com – Emre Jun 30 '11 at 18:53
@Emre: This is not a good suggestion. cstheory.SE is intended for research level questions, which this one definitely isn't, so it would be downvoted and closed in a blow. This doesn't make it a bad question, of course, far from it! – t.b. Jun 30 '11 at 20:44
It is more common (AFAIK) to use uppercase $\Theta$ rather than lowercase $\theta$ for "big-Theta" notation. – Yuval Filmus Nov 2 '11 at 14:42
The Problems 7-1 on CLRS gives a Hoare's implement of quicksort. The running time of Hoare's is $\Theta(n\log n)$ when all elements have same value. – Frank Science Jun 28 '12 at 4:48

The answer depends on how you are selecting the pivot. If you follow the algorithm present in the CLSR which always selects the last element as the pivot then it would result in the equation $T(N)=T(N-1)+N$ and hence $T(N)=O(N^2)$ else if you select the middle element as the pivot every time the equation will become $T(N)=2T(N/2)+N$ which would result in $T(N)=\Theta(N\log N)$.