The average-case time complexity of Quick Sort is?
The average-case time complexity of Quick Sort is?
Choose an Option
Answer
O(n log n)
Theory
Quick Sort uses divide-and-conquer with recurrence T(n) = 2T(n/2) + O(n) on average.
Solution
Solving the recurrence gives O(n log n).