Quick sort

Question

When array is already sorted in reverse order then what will be the recurrence relation for number of swaps on array of n elements using quick sort?

Comments

it will be,

T(n) = T(n-1) + O(n)

---

Ya it will be T(n)=T(n-1)+O(n)

By solving T(n)=O(n^2)

Answer 1

If the array is already sorted and we are using fixed partition method quick sort, then the partition takes place in such a way that one side of the pivot contains n-1 elements and other side contains 0 elements and pivot is in the correct  position that gives recurrence as
T(n)=T(n-1)+n

Comments

I m asking if the array is already sorted in reverse order.

---

It does not matter if it is reverse sorted or sorted.If you are choosing the pivot as the last element in either of these cases your sub-problem size shall be T(0) and T(n-1).

https://www.khanacademy.org/computing/computer-science/algorithms/quick-sort/a/overview-of-quicksort