We know that the lower bound for comparison-based sorting algorithms is Ω(nlogn), where logn being the binary logarithm of n. But what about for the best-case scenario of the bubble sort, which takes O(n) time? Of course, n is faster than nlogn. Why is that?

However, I don't know if this bound only applies for the worst-case scenario. I haven't ever learned the lower bound for the best- or average-case scenario. Is it different from the other?

(This question comes from the http://cstheory.stackexchange.com)

  • $\begingroup$ Yep, this is a lower bound for the worst case. In essence, no comparison-based algorithm can go faster in the worst case (i.e., always). So there is no contradiction. $\endgroup$ – Juho Dec 15 '15 at 17:40
  • $\begingroup$ @Juho, yes, but n<nlogn, so isn't the best-case of bubble sort faster than nlogn? $\endgroup$ – George Dec 15 '15 at 17:41
  • $\begingroup$ Yes, time complexity of $\Theta(n)$ is better than $\Theta(n \log n)$. Note that running in linear time in some case does not mean you run in linear time in every case. $\endgroup$ – Juho Dec 15 '15 at 17:41
  • $\begingroup$ I am sorry, but I didn't understand your aswer. (I am a beginner in algorithms.) $\endgroup$ – George Dec 15 '15 at 17:50
  • 1
    $\begingroup$ What exactly is your question? "Why is that?" Why is what? It is perfectly possible to have an algorithm that runs in linear time in some "best case". The same algorithm will not beat the lower bound in every case, only in some particular cases, like the "best case". Does that make sense? $\endgroup$ – Juho Dec 15 '15 at 17:52

The lower bound of sorting algorithm comparison based is $O(nlogn)$.
The best case lower bound is $O(n)$ which comes from fact that you need to check if numbers are sorted, so you traverse all of them to find out if they are ordered.

The lower bound is applied to all instances of problem, not just lucky particular case.

| cite | improve this answer | |

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.