Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

As a programmer with non CS background, I am learning algorithms.

When explaining the performance of quicksort in an Algorithm book and also elsewhere on the web, I do not see any reference to the time/space needed for shuffling. I do understand that shuffling is important to have the $O(n\log n)$ performance, but shuffling itself would have a complexity of $O(n)$. Why does this become irrelevant in the total performance?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

Here's a little more detail than Dave Clarke's answer.

Remember that $O(n\log n)$ means that there are constants $c_1$ and $n_1$ such that, for all $n\geq n_1$, the running time of the sorting phase is at most $c_1n\log n$ steps.1 Similarly, the running time of the shuffling phase is at most $c_2n$ steps, for all $n\geq n_2$. That means that, as long as $n>n_1$ and $n>n_2$, the total running time is at most $c_1n\log n + c_2n$. As long as $n\ge2$, $\log n\ge1$ (I'm assuming logs to base 2; if you want to take logs to some other base $b$, you need $n\ge b$), we have \begin{equation*} c_1n\log n + c_2n \le c_1n\log n + c_2n\log n = (c_1+c_2)n\log n\,, \end{equation*} as long as $n\ge \max\,\{n_1, n_2, 2\}$.

We conclude that the total running time is $O(n\log n)$.


1 Strictly speaking, this is something like the expected running time: as is well known, the worst-case running time is actually $O(n^2)$.

share|improve this answer

The short answer is that the $O(n\log n)$ component dominates the $O(n)$ component, hence the $O(n)$ part can be ignored in the statement of complexity.

share|improve this answer
1  
Also, the effect of actually shuffling is usually achieved by picking a uniformly random pivot. –  Louis Apr 3 at 9:55

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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