How is it that quicksort's worst-case and average-case running times differ? Let's start by looking at the worst-case running time. Suppose that we're really unlucky and the partition sizes are really unbalanced. In particular, suppose that the pivot chosen by the partition function is always either the smallest or the largest element in the n-element subarray. Then one of the partitions will contain no elements and the other partition will contain n1n−1 elements—all but the pivot. So the recursive calls will be on subarrays of sizes 00 and n1n−1. As in merge sort, the time for a given recursive call on an n-element subarray is Θ(n)\Theta(n). In merge sort, that was the time for merging, but in quicksort it's the time for partitioning.

Worst-case running time

When quicksort always has the most unbalanced partitions possible, then the original call takes cncn time for some constant cc, the recursive call on n1n−1 elements takes c(n1)c(n−1) time, the recursive call on n2n−2 elements takes c(n2)c(n−2) time, and so on. Here's a tree of the subproblem sizes with their partitioning times:

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy