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:

Improve this question
$\endgroup$
4
  • $\begingroup$ Please include the CLRS implementation of quicksort. Some of us don't have a copy. $\endgroup$
    – Yuval Filmus
    Dec 13, 2014 at 17:08
  • $\begingroup$ You are right. Pseudocode links added. Thank you $\endgroup$
    – Acamol
    Dec 13, 2014 at 17:18
  • $\begingroup$ Your recurrence is wrong when $m>n/2$. $\endgroup$
    – Yuval Filmus
    Dec 13, 2014 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, 2014 at 17:34

1 Answer 1

Reset to default
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)$.

Improve this answer
$\endgroup$
5
  • $\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, 2014 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, 2014 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, 2014 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, 2014 at 19:06
  • $\begingroup$ Toda raba. I'll complete my signing up as soon as I get home and upvote. $\endgroup$
    – Acamol
    Dec 13, 2014 at 19:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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