# Lower Bound for Comparison-based sorting algorithms

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)

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

## 1 Answer

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.