What is the average case time complexity of quicksort?

The average-case time complexity of quicksort is O(n log n), which is attributed to the way the algorithm partitions the data and recursively sorts the subarrays.

In quicksort, the process involves selecting a 'pivot' element from the array and partitioning the other elements into two subarrays, according to whether they are less than or greater than the pivot. This partitioning on average results in each subarray being approximately half the size of the original array, leading to logarithmic depth in terms of the number of partitioning operations required.

Each partitioning operation itself takes linear time, O(n), as each element must be compared to the pivot. When combining both the logarithmic depth of the partitions (log n levels of recursion) with the linear work done at each level (O(n)), the total average-case complexity becomes O(n log n).

This characteristic makes quicksort an efficient sorting algorithm for large datasets, and its average-case performance is competitive with other algorithms such as mergesort and heapsort. Conversely, options like O(n^2) reflect the worst-case scenario that can occur with poor pivot choices, while O(n) and O(log n) do not capture the recursive nature of quicksort in typical use cases.