2
$\begingroup$

So I'm trying to figure out why the worst case of Quicksort is $O(n^2)$.

I know this a very well known problem, but the funny thing is where ever I look (even Wikipedia) gives the following explanation: "The worst case is the most unbalanced case where the problem splits to a problem of size $n-1$ and a problem of size $0$ (i.e. when the array is already sorted)".

Then they use the master theorem and find it is $O(n^2)$.

Marvelous. So simple. But wait.

Do we know upfront that the worst case is $O(n^2)$? No, that's what we need to prove.

"The most unbalanced case" meaning it is the worst case? Is there any theorem that states this?

So what is actually a coherent proof that Quicksort is $O(n^2)$?

Or in other words, what is the proof for the missing part?

We can derive that the run time can be described as $T(n) = T(n_1) + T(n_2) + O(n)$ where $n_1 + n_2 + 1 = n$. How to prove $T(n)$ is the largest when $n_1 = 0$ and $n_2 = n-1$?

I already know this is the most unbalanced case. Why is it actually the worst case?

$\endgroup$
2
$\begingroup$

The running time of quicksort satisfies the recurrence $$ T(n) \leq \max_{n_1+n_2+1=n} T(n_1) + T(n_2) + Cn, $$ with base cases of $T(1) = C$ and $T(0) = 0$, say. Let us now prove by induction that $T(n) \leq Cn^2$. The base cases obviously hold. As for the inductive step, \begin{align} T(n) &\leq \max_{n_1+n_2+1=n} C(n_1^2 + n_2^2) + Cn \\ &= \max_{0 \leq m \leq n-1} C(m^2 + (n-1-m)^2) + Cn \\ &= C(n-1)^2 + Cn + \max_{0 \leq m \leq n-1} 2Cm(m-(n-1)) \\ &\leq C(n-1)^2 + Cn \\ &\leq Cn^2. \end{align}


Why is the worst case when $n_1 \in \{0,n-1\}$? This is because the function $n^2$ is convex, that is, the maximum of $x^2+(n-x)^2$ over $x \in [0,n]$ is attained at one of the endpoints. In more complicated situations, we could trying showing this directly, by inductively showing that $T(n+2)-T(n+1) \geq T(n+1)-T(n)$, which should imply (I think) that the maximum of $T(n_1)+T(n_2)$ is attained at one of the endpoints.

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