Proving Quicksort is $O(n^2)$
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) &amp;\leq \max_{n_1+n_2+1=n} C(n_1^2 + n_2^2) + Cn \\ &amp;=
\max_{0 \leq m \leq n-1} C(m^2 + (n-1-m)^2) + Cn \\ &amp;=
C(n-1)^2 + Cn + \max_{0 \leq m \leq n-1} 2Cm(m-(n-1)) \\ &amp;\leq
C(n-1)^2 + Cn \\ &amp;\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.