[Solved]: Solving Recurrence Relation (quicksort )

Problem Detail: 

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?

Asked By : lo tolmencre

Answered By : Yuval Filmus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/61120

3.2K people like this

 Download Related Notes/Documents