4
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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)$.

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Also, the effect of actually shuffling is usually achieved by picking a uniformly random pivot. $\endgroup$
    – Louis
    Apr 3 '14 at 9:55

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.