Cormen Edition 3 Exercise 7.2 Question 2 (Page No. 178)

Question

What is the running time of QUICKSORT when all elements of the array $A$ have the same value?

Comments

$O(n^2)$

---

https://math.stackexchange.com/questions/22596/quicksort-running-time

Answer 1

Total comparison =( n-1)+(n-2) +.....n

                                   =O(n²)

Quick sort will do worst case time complexity if array is already sorted ie O(n²)

Answer 2

All the Elements have same values ,treated as sorted therefore worst case complexity , ie O(n^2)