Question

The average case time complexity of quick sort is

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

Hint:

Quick sort’s efficiency comes from partitioning the array into smaller sub-arrays, leading to a logarithmic depth.

Answer 1

The Correct Option is A

Quick sort is an efficient sorting algorithm with an average case time complexity of \( O(n \log n) \). This is because, on average, the pivot divides the list in roughly half, resulting in logarithmic recursion depth.
Thus, the average case time complexity is \( O(n \log n) \).