1
$\begingroup$

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:

  1. 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$.
  2. 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:

$\endgroup$
  • $\begingroup$ Please include the CLRS implementation of quicksort. Some of us don't have a copy. $\endgroup$ – Yuval Filmus Dec 13 '14 at 17:08
  • $\begingroup$ You are right. Pseudocode links added. Thank you $\endgroup$ – Acamol Dec 13 '14 at 17:18
  • $\begingroup$ Your recurrence is wrong when $m>n/2$. $\endgroup$ – Yuval Filmus Dec 13 '14 at 17:28
  • $\begingroup$ You are correct, I should have stated that I'm ignoring this case because it's less interesting than $m <= n/2 $. I tried to keep the post short which in turn led me to compromise formalism and allowed several mistakes in, most of them are less notable than the one you stated. Hopefully the other mistakes won't matter asymptotically. $\endgroup$ – Acamol Dec 13 '14 at 17:34
1
$\begingroup$

A more correct recurrence is $$T(n,m) = \begin{cases} T(n-m,m) + \Theta(m^2+n) & m \leq n/2, \\ \Theta(m^2+n) & m > 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) &= T((k-1)m,m) + m^2 + km \\ &= T((k-2)m,m) + 2m^2 + km + (k-1)m \\ &= \cdots \\ &= T(m,m) + (k-1)m^2 + km + \cdots + 2m \\ &= km^2 + km + \cdots + m \\ &= km^2 + \frac{1}{2}k(k-1)m \\ &= \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)$.

$\endgroup$
  • $\begingroup$ Thank you for the detailed response. I have a few questions if you will: 1. I assume you derived $\theta(m^2+n)$ for the case $m <= n/2$ in a similiar fashion as I did in my formula?(instead of θ(m2)+θ(n) in mine). If so, how did you get $\theta(m^2+n)$ for the case $m > n/2$ ? 2. $\endgroup$ – Acamol Dec 13 '14 at 18:55
  • $\begingroup$ When $m\leq n/2$ our formulas are equivalent: $\Theta(m^2)+\Theta(n)=\Theta(m^2+n) $. In the other case we get a sorted or almost sorted list, and so the complexity is $\Theta(n^2) $, which in this regime is the same as what I wrote. $\endgroup$ – Yuval Filmus Dec 13 '14 at 18:59
  • $\begingroup$ 2. How did you realize $\theta(n^{3/2})$ is the lower bound? I can see that if I substitute $\sqrt{n}$ for $m$ I get this answer, but what was the reasoning that led you to this bound? 3. Is $m$ considered dependent on $n$? $\endgroup$ – Acamol Dec 13 '14 at 19:02
  • $\begingroup$ $m$ is independent of $n$, though it's constrained by it. The $n^{3/2} $ is an exercise for you. $\endgroup$ – Yuval Filmus Dec 13 '14 at 19:06
  • $\begingroup$ Toda raba. I'll complete my signing up as soon as I get home and upvote. $\endgroup$ – Acamol Dec 13 '14 at 19:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.