Question

How many comparisons are there in randomised quick sort?

Answer 1

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 n-element subarray. Then one of the partitions will contain no elements and the other partition will contain n-1 n−1 elements—all but the pivot. So the recursive calls will be on subarrays of sizes 0 and n-1 n−1.