title: comparison sort algorithms requires Ω(nlgn) comparisons in the worst case
body: <p>This was taken from the popular book called Intro to Algorithms. The author states that any comparison sort algorithm requires Ω(nlgn) comparisons in the worst case. Taking the bubble sort algorithm as an example, in the worst case we have an upper bound O(n^2). Omega represents the lower or least bound therefore wouldn't the lower bound of a worst case be Ω(n^2) as well? How would a bubble sort have a lower bound, such as the suggested Ω(nlgn), rather than n^2 in a worst case performance? In the worst case performance bubble sort can't take AT LEAST nlgn.</p>