The Stack Overflow podcast is back! Listen to an interview with our new CEO.
3 of 5 deleted 1 character in body


The expected running time of quicksort with random pivot is actually $O(n\log n)$.

One can show that you cannot achieve better expected runtime, by any randomized algorithm that correctly sorts any list of $n$ elements. This is shown by Yao's principle, which states that the worst case expected running time of any randomized algorithm, is no better than the expected running time of the best deterministic algorithm for any input distribution.

This gives you the power to, instead of considering coin tossing algorithms, fix some input distribution, and ask what is the best expected running time of any deterministic algorithm relative to that distribution (i.e. it relates randomize complexity to distributional complexity).

Now, since we can fix any distribution, you can look at the uniform distribution over all possible inputs, and ask what is the best expected running time a deterministic algorithm achieves, relative to the uniform distribution. A lower bound proof in this setting is closer in spirit to the regular lower bound proof for deterministic sorting that you know, you can find it in the following lecture notes.

The idea is similar, you consider a comparison based sorting algorithm as a binary tree, where each node is a query of the form $x<y$, and each leaf in the tree represents a different permutation. The number of comparisons required to sort some input $a_1,...,a_n$ is given by the height of the leaf corresponding to the sorted permutation $a_{i_1},...,a_{i_n}$. Since the number of leaves is $n!$, you know the depth is $\Omega(n\log n)$. The difference in the distributional case is that you need to bound the average leaf height of a binary tree with $n!$ leaves (not the depth). Now, proceed to show that the average leaf height is minimized by a balanced binary tree, in which the average leaf height is $\Omega(\log n!)$. To see why you can focus on balanced trees, show that if the tree is unbalanced somewhere, you can "fix it", and this operation only decreases average leaf height.

I only dealt with algorithms that correctly sort all inputs, but using Yao's principle for Monte-Carlo algoirthms, you can extend this to your case.