Why are unbalanced partitions worse than balanced partitions in Quicksort? I am unable to understand why unbalanced partitions in quicksort is actually worse than balanced partitions.

After reading this document it shows that worse case partitions are of the type $(0,(n-1)), (0,(n-2)), (0,(n-3))$ and so on. So the work on every step is $Cn, C(n-1), C(n-2)$ , it actually decreases since $C(n) &gt; C(n-1)$. Correct me if I am wrong.

While in best case the partitions on every step can be assumed as $n/2$ on each side or $n/2$ or $n/2 - 1$ on each side. So the work done on each step, is $Cn$ 
 always. 

So how is that better than unbalanced partitions ? The work actually decreases in every step for unbalanced partitions, while for balanced partitions the work actually remains constant on all the steps and depending on the partition algo it may even include the pivot which is already sorted.
for balanced partitions the work actually remains constant on all the steps


That's just false. Have another look at the algorithm: each recursive call gets an input that is properly smaller than the current one.

You also seem to be missing that, for the total cost, you need to add up all the steps. Just saying, "the inputs get smaller", doesn't tell you anything besides that the algorithm terminates.

In the worst case, you get the solution of a recurrence similar to

$\qquad\begin{align*}
 T(1) &amp;= 0 \\
 T(i) &amp;= T(i-1) + i
\end{align*}$

which solves to some $T \in \Theta(n^2)$.

In the average case, you get the solution of a recurrence similar to

$\qquad\begin{align*}
 T(1) &amp;= 0 \\
 T(i) &amp;= 2T(i/2) + i
\end{align*}$

which solves to some $T \in \Theta(n \log n)$.



To stress my point from above, consider

$\qquad\begin{align*}
 T(1) &amp;= 0 \\
 T(i) &amp;= T(i/2) + i
\end{align*}$

which solves to some $T \in \Theta(n)$.

Or

$\qquad\begin{align*}
 T(1) &amp;= 0 \\
 T(i) &amp;= T(i/2) + 1
\end{align*}$

which solves to some $T \in \Theta(\log n)$.

You see that the specifics of the recurrence matter.