# Proving Quicksort is $O(n^2)$

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?

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.