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 > \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) &= T(n-m, m) + \theta (m^2) + \theta (n) \\ &= \cdots \\ &= 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: