Asymptotic analysis for quicksort on special case I have the following problem for homework:

Given an array of the form  $[m+1, m+2,..., n, 1, 2,..., m]$ as an input,
analyze quicksort's run time complexity.
TIP: check for $m &gt; \frac{n}{2}$  and  $m \le \frac{n}{2}$ 

The quicksort algorithm is the deterministic version from CLRS.

I have a sense of what's going on but I'm having trouble proving it properly.

I arrived at the following formula:
$$\begin{align*}
    T(n, m) &amp;= T(n-m, m) + \theta (m^2) + \theta (n) \\
            &amp;= \cdots \\
            &amp;= T(n-(i+1)m, m) + i\theta(m^2) + \sum_{k=0}^{i} \theta(n-km)
\end{align*}$$ from the following reasoning:

at each "step" $i$ the partition will swap the $m$ smallest numbers (located at the end of the sub-array)  with the next $m$ smallest numbers (located at the beginning of the sub-array), keeping their sorted order.
The sub array is of size $n-im$, so the partition takes $\theta(n-im)$.
Then perform the first recursive call on the $m-1$ smallest numbers on the left of the sub-array for ~$\theta(m^2)$.
Next we perform the next recursive call on an sub-array of size $(n-(i+1)m)$.

We can easily see when this will end with a mod operation.
(I understand there is a bit additional work even after we can't sub $m$ smallest numbers anymore but that's not very important so omitted).

Now, my issues are:


I don't understand how to treat $m$ and $n$. $m$ is somewhat dependent on $n$ because it cannot grow indefinitely without $n$ growing as well. But on the other hand, it doesn't depend directly on $n$.
If I substitute the end condition I get an expression with both $n$ and $m$ which I believe I should find a way to express in terms of $n$ alone but I don't know how.


I know I omitted alot of reasoning, details and formalism but it's got quite long anyhow so I hope it's clear enough. 
If not, I will be more than happy to clarify.

I'd appreciate any help or suggestions.

EDIT: here is the pseudocode for partition and quicksort:


Partition: http://qph.is.quoracdn.net/main-qimg-65c54b3e9b6fef01a5ff7543ed3a3092?convert_to_webp=true
Quicksort: http://www2.hawaii.edu/~suthers/courses/ics311s14/Notes/Topic-10/pseudocode-quicksort.jpg
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)$.