Quicksort is a divide-and-conquer sorting algorithm. It works by selecting a pivot element, partitioning the array into two subarrays (elements less than the pivot and elements greater than the pivot), and then recursively sorting those subarrays. In the average case, the partition step splits the array into roughly equal halves, so the recurrence is commonly written as (T(n) = T(n/2) + T(n/2) + O(n)), where (O(n)) is the cost of partitioning. This solves to (O(n \log n)), which is why quicksort is widely taught as an efficient general-purpose sorting method.

However, textbooks also emphasize that quicksort has a worst-case time complexity of (O(n^2)) when partitions are extremely unbalanced (for example, repeatedly choosing the smallest or largest element as the pivot on already sorted input). Practical implementations reduce the likelihood of worst-case behavior using randomized pivots or “median-of-three” pivot selection. Despite the worst-case, quicksort is often very fast in practice because it has good cache performance and low constant factors, and it sorts in place with only (O(\log n)) average recursion stack space.

Among the provided options, the correct expected complexity for quicksort (average-case, and commonly cited in coursework questions) is (O(n \log n)). The other options are too small to represent the cost of sorting arbitrary data.