Analysis of Quicksort

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 $n−1$ elements—all but the pivot. So the recursive calls will be on subarrays of sizes $0$ and $n−1$. As in merge sort, the time for a given recursive call on an n-element subarray is $\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 $cn$ time for some constant $c$, the recursive call on $n−1$ elements takes $c(n−1)$ time, the recursive call on $n−2$ elements takes $c(n−2)$ time, and so on. Here's a tree of the subproblem sizes with their partitioning times:

When we total up the partitioning times for each level, we get:

The last line is because $1+2+3+ \cdots +n$ is the arithmetic series, as we saw when we analyzed selection sort. (We subtract $1$ because for quicksort, the summation starts at $2$, not $1$.) We have some low-order terms and constant coefficients, but when we use big–$\Theta$ notation, we ignore them. In big–$\Theta$ notation, quicksort's worst-case running time is $\Theta(n2)$.

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 ...