What is the time complexity of the Quick Sort algorithm in the average case ?

Quick Sort is a divide-and-conquer algorithm that works by selecting a 'pivot' element and partitioning the array around it. In the average case, the pivot divides the array into two roughly equal halves at each level of recursion. This results in a recursion tree with a depth of approximately log n, where n is the number of elements. Since partitioning takes linear time O(n) at each level, and there are log n levels, the total average-case time complexity becomes O(n log n). Option A (O(n)) is incorrect because Quick Sort requires more than a single pass to sort. Option D (O(log n)) is too optimistic as it ignores the work done at each partitioning step. While Option C (O(n²/2)) resembles the worst-case scenario, it is not representative of average performance. Thus, O(n log n) accurately reflects the expected efficiency for random inputs.