What are the average-case and worst-case time complexities of quicksort?

What are the average-case and worst-case time complexities of quicksort?

• A. Average O(n^2); worst-case O(n log n)
• B. Average O(n log n); worst-case O(n^2)
• C. Average O(n); worst-case O(n^2)
• D. Average O(log n); worst-case O(n)

Answer: (B)

Quicksort’s performance depends on how balanced the partitions are after choosing a pivot. When the pivot splits the array roughly in half on average, each level of recursion processes all n elements for partitioning, and there are about log2 n levels. This leads to a total running time on the order of n log n, which is described by the recurrence T(n) = 2T(n/2) + O(n). That’s why the average case is O(n log n). In the worst case, if the pivot is always the smallest or largest element, one side has size n−1 and the other has size 0. The recursion runs to depth n, and each level costs O(n) for partitioning, so the total sums to n + (n−1) + ... + 1 = O(n^2). This is why the worst case is O(n^2). So the average-case time is O(n log n) and the worst-case time is O(n^2).

Quicksort’s performance depends on how balanced the partitions are after choosing a pivot. When the pivot splits the array roughly in half on average, each level of recursion processes all n elements for partitioning, and there are about log2 n levels. This leads to a total running time on the order of n log n, which is described by the recurrence T(n) = 2T(n/2) + O(n). That’s why the average case is O(n log n).

In the worst case, if the pivot is always the smallest or largest element, one side has size n−1 and the other has size 0. The recursion runs to depth n, and each level costs O(n) for partitioning, so the total sums to n + (n−1) + ... + 1 = O(n^2). This is why the worst case is O(n^2).

So the average-case time is O(n log n) and the worst-case time is O(n^2).