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?