1
$\begingroup$

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)

Improve this question
$\endgroup$
7
  • $\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
    Commented Dec 15, 2015 at 17:40
  • $\begingroup$ @Juho, yes, but n<nlogn, so isn't the best-case of bubble sort faster than nlogn? $\endgroup$
    – George
    Commented Dec 15, 2015 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
    Commented Dec 15, 2015 at 17:41
  • $\begingroup$ I am sorry, but I didn't understand your aswer. (I am a beginner in algorithms.) $\endgroup$
    – George
    Commented Dec 15, 2015 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
    Commented Dec 15, 2015 at 17:52

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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