Problem Detail: 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(nlog n)$ performance, but shuffling itself would have a complexity of $O(n)$. Why does this become irrelevant in the total performance?
Asked By : zencv
Answered By : David Richerby
Here’s a little more detail than Dave Clarke’s answer. Remember that $O(nlog n)$ means that there are constants $c_1$ and $n_1$ such that, for all $ngeq n_1$, the running time of the sorting phase is at most $c_1nlog n$ steps.1 Similarly, the running time of the shuffling phase is at most $c_2n$ steps, for all $ngeq n_2$. That means that, as long as $n>n_1$ and $n>n_2$, the total running time is at most $c_1nlog n + c_2n$. As long as $nge2$, $log nge1$ (I’m assuming logs to base 2; if you want to take logs to some other base $b$, you need $nge b$), we have begin{equation*} c_1nlog n + c_2n le c_1nlog n + c_2nlog n = (c_1+c_2)nlog n,, end{equation*} as long as $nge max,{n_1, n_2, 2}$. We conclude that the total running time is $O(nlog 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)$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/23387
