Friday 18 January 2013

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(n1)+Θ(n)

The above recurrence has the solution (I will prove this later):
T(n)=Θ(n2)

Hence the running time of QUICKSORT in this case is
Θ(n2)