In the 3rd lecture of Wednesday, it was said that for bubble sort, lower bound or omega will be 'n'.

But shouldn't it be (n-1)? Suppose if list to sort is (1, 2, 3, 4) then it would take me 3 comparisons to identify that this is a already sorted list.

No? If correct me if I am missing something.


In Big O notation and Omega notation the constants are not computed. Say you have an array with 1000 places. It's not that different to say 1000 than 999. So the n-1 becomes n. Also let's say that you have to traverse an array, that is to read all of its elements. If the array is 1000 places, ti has an Ω(1000), but we still say that it is constant time as Ω(10000) is considered the same thing as Ω(1).

  • Ok, agree. There are more to it, like in selection sort there are 'n' swaps as well apart from comparisons, but they are ignored because of their insignificance in front of n^2. So, I could accept that Ω(n-1) for bubble sort will be Ω(n) but if we say with precision then there will be (n-1) comparisons. Right?
    – hagrawal
    Jul 10 '15 at 17:47
  • Correct. That means that the real world application is different than the omega notation, as clearly 1000 is 1000 times larger than one, but still considered the same.
    – ChrisG
    Jul 10 '15 at 17:49
  • Ok, thanks for clarification.
    – hagrawal
    Jul 10 '15 at 17:52
  • Glad I could help.
    – ChrisG
    Jul 10 '15 at 17:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .