I have to solve the following question in an assignment:
Calculate the time and space complexities of the Quick Sort for following input. Also, discuss the method of calculating the complexity.
(a) When input array is already sorted.
(b) When input array is reverse sorted.
(c) When all the elements in the input array are the same.
I am having trouble in calculating the time complexities of the different cases. The following table shows pivot vs case, with cells in bold being the one where I have doubts.
| TIME | First | Middle | Last |
|---|---|---|---|
| Sorted | O(n^2) | O(n*logn) | O(n^2) |
| Same | O(n^2) | O(n^2) | O(n^2) |
| Reverse | O(n^2) | O(n*logn) | O(n^2) |
Are these right? If not, what am I doing wrong?