Proving Quicksort is $O(n^2)$

Question

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?

Answer 1

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.