Why is the average-case running time of quicksort $O(n \log_2 n)$?

Question

What is a mathematically rigorous explanation of why quicksort's average-case running time is $O(n \log_2 n)$?

Answer 1

To do average case analysis, we need to consider all possible permutation of the input array and calculate the time taken by every permutation which is not easy. We can get an idea of average case by considering the case when partition cuts $O(\frac{n}{9})$ elements in one set and $O(\frac{9n}{10})$ elements in other set. Following this we get \begin{equation} T(n) = T(\frac{n}{9}) + T(\frac{9n}{10}) + O(n) \end{equation} which is shown to be $O(n \log n)$. If you average over all such permutations, you will also get $O(n \log n)$.