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: