Question

Write down a recurrence relation for this version of QuickSort, and solve it asymp-totically. Show your work. Assume that the time it takes to find the pivot (eitherbest or worst, depending on the level of recursion) is Θ(n) for lists of lengthn.

Answer 1

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)