What is the average-case time complexity of QuickSort?

• A. O(n^2)
• B. O(log n)
• C. O(n)
• D. O(n log n)

Answer: (D)

QuickSort’s performance depends on how evenly the pivot divides the array at each step. When the pivot splits the array into two roughly equal parts, the recursion goes about log n levels deep. Each level still processes all elements once for partitioning, so the total work is proportional to n at every level times the number of levels, giving n log n operations on average. This balance happens with random pivots or good pivot choices, which is why the average-case time complexity is O(n log n).

The other patterns are not representative of the average. If the partitions are extremely unbalanced every time, the cost grows toward O(n^2), which is the worst case. O(log n) or O(n) would imply far less work than actually occurs across the recursive levels, so they don’t describe the typical behavior.