What is the average-case time complexity of QuickSort?

The average-case time complexity of QuickSort is O(n log n), and this is primarily due to the way the algorithm operates on the input data. QuickSort is a divide-and-conquer algorithm that involves selecting a 'pivot' element and partitioning the array into two subarrays: elements less than the pivot and elements greater than the pivot. This partitioning process is done in linear time, O(n), as each element has to be compared to the pivot to determine its position in the two subarrays.

After partitioning, the algorithm recursively sorts the two subarrays. As a result, the average-case scenario occurs when the pivot choice divides the array into two roughly equal halves. This balance helps minimize the depth of the recursive calls.

When you consider the nature of the recursive calls in QuickSort, each level of recursion effectively works on half of the elements of the array. Thus, for a scenario where the pivot is well-chosen on average, the depth of recursion will be log(n). Since each level of recursion involves O(n) work to partition the array, the overall average-case time complexity becomes O(n log n).

This makes QuickSort efficient for sorting large datasets on average, even though its worst-case time complexity can be O