5
$\begingroup$

I know quicksort to have a runtime of $\mathcal{O}(n \log_2 n)$

However trying to solve for it I get something different and I am not sure why that is.

Ok, so solving recurrence relations can be done several different ways.

The recurrence relation for quicksort is:

$$T(n) = 2 T(\frac{n}{2}) + \mathcal{O}(n)$$

Reinserting a few times we get:

$$T(n) = 2 \left[ 2 T(\frac{n}{4}) + \mathcal{O}(\frac{n}{2}) \right] + \mathcal{O}(n)$$

$$T(n) = 2 \left[ 2 \left[ 2 T(\frac{n}{8}) + \mathcal{O}(\frac{n}{4}) \right] + \mathcal{O}(\frac{n}{2}) \right] + \mathcal{O}(n)$$

$$...$$

Which can be generalised to:

$$T(n) = 2^kT(\frac{n}{2^k})+\sum_{i=0}^{k-1} \mathcal{O}(\frac{n}{2^i})$$

Now the sum can be solved like this:

$$\sum_{i=0}^{k-1} \mathcal{O}\left(\frac{n}{2^i}\right) = \sum_{i=0}^{k-1} \mathcal{O}\left(n\left(\frac{1}{2}\right)^i\right) = \frac{n -n\left( \frac{1}{2}\right)^{k-1}}{1 - \frac{1}{2}}$$

$$\lim_{k \to \infty} \frac{n -n\left( \frac{1}{2}\right)^{k-1}}{1 - \frac{1}{2}} = \frac{n}{1 - \frac{1}{2}} = 2n$$

So the recurrence can be simplified accordingly:

$$T(n) = 2^kT(\frac{n}{2^k})+2n$$

Assuming $T(1) = C$ we get $$T(n) = 2^{\log_2 n}T(\frac{n}{2^{\log_2 n}})+2n = n C + 2n$$

And $ n C + 2n \not \in \mathcal{O}(n \log_2 n)$

Can somebody explain my error to me?

$\endgroup$
  • 1
    $\begingroup$ "And $nC+2n\notin\mathcal{O}(n\log_2 n)$". Incorrect. (But, still, $nC+2n$ isn't the solution to the recurrence, so the question survives.) $\endgroup$ – David Richerby Jul 31 '16 at 15:11
4
$\begingroup$

Your mistake is $2\mathcal{O}(n/2) = \mathcal{O}(n/2)$. More generally, in order not to be confused, it is much better to replace $\mathcal{O}(n)$ with $An$ for some constant $A$, which can be taken as $1$ without loss of generality. Then we have $$ \begin{align*} T(n) &\leq 2T\left(\frac{n}{2}\right) + n \\ &\leq 4T\left(\frac{n}{4}\right) + 2 \frac{n}{2} + n \\ &\leq 8T\left(\frac{n}{8}\right) + 4 \frac{n}{4} + 2 \frac{n}{2} + n \\ &\leq \dots \end{align*} $$ More generally, we get $$ T(n) \leq 2^k T\left(\frac{n}{2^k}\right) + kn. $$ Assuming $n = 2^k$ and $T(1) = C$, this gives $$ T(n) \leq 2^kC + k2^k = \mathcal{O}(n\log n). $$ You can get a lower bound in exactly the same way.

$\endgroup$

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.