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)