# Analysis of Quicksort

## We'll cover the following

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

## Worst-case running time

When quicksort always has the most unbalanced partitions possible, then the original call takes

Create a free account to access the full course.

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