What is the typical average-case time complexity of quicksort and what pivot strategy helps achieve it?

• A. Average-case time complexity is O(n log n); use a good pivot such as median-of-three or random pivot.
• B. Average-case time complexity is O(n^2); pivot choice does not matter.
• C. Worst-case time complexity is O(n log n) with a bad pivot.
• D. Time complexity is O(log n) for all cases.

Answer: (A)

The main idea is that quicksort’s efficiency comes from balanced partitions. Each pass partitions the array once, and the number of levels in the recursion corresponds to how evenly the data is split. When the pivot splits the data roughly in half on average, there are about log2 n levels of recursion, and each level processes all n elements, giving an overall time of O(n log n). Choosing a good pivot—like median-of-three or a random pivot—increases the chance of those balanced splits, so you typically achieve that n log n behavior rather than a slower or faster pattern. If the pivot is consistently poor, partitions become very uneven and the time can degrade toward O(n^2). Statements claiming O(n^2) on average or O(log n) for all cases don’t reflect how the algorithm behaves in practice.