Asymptotic analysis for quicksort on special case
A more correct recurrence is
$$T(n,m) = \begin{cases} T(n-m,m) + \Theta(m^2+n) &amp; m \leq n/2, \\ \Theta(m^2+n) &amp; m &gt; n/2. \end{cases}$$
In order to solve the recurrence, let us assume that the hidden constants are all $1$, and that $n = km$. Then
$$
\begin{align*}
T(km,m) &amp;= T((k-1)m,m) + m^2 + km \\
&amp;= T((k-2)m,m) + 2m^2 + km + (k-1)m \\
&amp;= \cdots \\
&amp;= T(m,m) + (k-1)m^2 + km + \cdots + 2m \\
&amp;= km^2 + km + \cdots + m \\
&amp;= km^2 + \frac{1}{2}k(k-1)m \\
&amp;= \Theta(km^2 + k^2m).
\end{align*}
$$
Substituting $k = n/m$ and hoping for the best, we get
$$ T(n,m) = \Theta(nm + n^2/m). $$
This quantity ranges from $\Theta(n^{3/2})$ to $\Theta(n^2)$.