Answer:As in merge sort, the time for a given recursive call on an n-element subarray is Θ(n). In merge sort, that was the time for merging, but in quicksort it's the time for partitioning.
Explanation:
Worst-case running time:
When quicksort always has the most unbalanced partitions possible, then the original call takes cncnc, n time for some constant ccc, the recursive call on n-1n−1n, minus, 1 elements takes c(n-1)c(n−1)c, left parenthesis, n, minus, 1, right parenthesis time, the recursive call on n-2n−2n, minus, 2 elements takes c(n-2)c(n−2)c, left parenthesis, n, minus, 2, right parenthesis time, and so on. cn+c(n−1)+c(n−2)+⋯+2c=c(n+(n−1)+(n−2)+⋯+2)
=c((n+1)(n/2)−1)
The last line is because 1 + 2 + 3 +...... n is the arithmetic series
Best-case running time:
Quicksort's best case occurs when the partitions are as evenly balanced as possible: their sizes either are equal or are within 1 of each other. The former case occurs if the subarray has an odd number of elements and the pivot is right in the middle after partitioning, and each partition has (n-1)/ 2 elements. The latter case occurs if the subarray has an even number n of elements and one partition has n/2 elements with the other having n/2-1.In either of these cases, each partition has at most n/2 elements.
Using big-Θ notation, we get the same result as for merge sort: Θ(nlog2n)
