1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.