4 ms·

I know the rest of the notations in the family but, to be honest, even in most algorithmics textbooks they tend to use Big O like 90% of the time, even in conte

I know the rest of the notations in the family but, to be honest, even in most algorithmics textbooks they tend to use Big O like 90% of the time, even in contexts where Big Theta would be more precise (e.g. "mergesort is O(n log n) in all cases"). Let alone in more informal contexts. I don't especially like it, but it's OK because it's not a lie. And I do think for people who just want the gist of the concept, like readers of this piece, it's enough and it's not worth being fussy about it. What irks me is people who use the equal sign as in T(n)=O(n log n), though. Why would a function equal a class? Set membership notation does the job just fine.

repsilat 6y ago
> even in contexts where Big Theta would be more precise (e.g. "mergesort is O(n log n) in all cases" Just to be careful here: the difference between big/little oh/theta/omega is orthogonal to best/worst/average case. A pedant could say that merge sort makes O(n^3) comparisons in both the best and worst case, ω(1) in both the best and worst case, etc. Colloquially, the former means "as fast as", and the latter means "slower than".
- gvx 6y ago
  I've seen this a lot, where people are convinced big Oh is specifically meant for worst cases performance. And there may be some logic behind it, because if some function is in Θ(n^3) in the worst case, then it is true that it is in O(n^3) in all cases, so maybe that is why they couple big Oh with worst case growth.
  - Al-Khwarizmi 6y ago
    Again, I think from a shallow perspective it makes sense. If an algorithm always runs in O(n^3), then it's guaranteed that it runs in O(n^3) in the worst case. And if an algorithm runs in O(n^3) in the worst case, then it's guaranteed to always run in O(n^3) (but not in Θ(n^3), of course). So if you only care about worst-case performance, it's reasonable to only use the big O. Of course, what your parent comment says is also true - you could say that mergesort is O(2^n), in the worst case or in any other case, and be correct because it's an upper bound. But people using Big Oh informally don't say that because you typically want to show how good your algorithm is, so you use the tightest upper bound possible (i.e. the big theta of the worst case).
thaumasiotes 6y ago
> What irks me is people who use the equal sign as in T(n)=O(n log n), though. Why would a function equal a class? Set membership notation does the job just fine. It's strange but it's fully standard. I would guess it develops from the use in analysis, where o(n) is more common. You derive your formula, it has a term in it that you don't want, you observe that "complicated term's numerator = o(n)", you take your limit, and the term vanishes away. Use of the = sign makes more sense there, because conceptually you're claiming something about the value of the term. (Specifically, that in the limit, it's equal to zero.)

repsilat 6y ago

> even in contexts where Big Theta would be more precise (e.g. "mergesort is O(n log n) in all cases" Just to be careful here: the difference between big/little oh/theta/omega is orthogonal to best/worst/average case. A pedant could say that merge sort makes O(n^3) comparisons in both the best and worst case, ω(1) in both the best and worst case, etc. Colloquially, the former means "as fast as", and the latter means "slower than".

gvx 6y ago
I've seen this a lot, where people are convinced big Oh is specifically meant for worst cases performance. And there may be some logic behind it, because if some function is in Θ(n^3) in the worst case, then it is true that it is in O(n^3) in all cases, so maybe that is why they couple big Oh with worst case growth.
- Al-Khwarizmi 6y ago
  Again, I think from a shallow perspective it makes sense. If an algorithm always runs in O(n^3), then it's guaranteed that it runs in O(n^3) in the worst case. And if an algorithm runs in O(n^3) in the worst case, then it's guaranteed to always run in O(n^3) (but not in Θ(n^3), of course). So if you only care about worst-case performance, it's reasonable to only use the big O. Of course, what your parent comment says is also true - you could say that mergesort is O(2^n), in the worst case or in any other case, and be correct because it's an upper bound. But people using Big Oh informally don't say that because you typically want to show how good your algorithm is, so you use the tightest upper bound possible (i.e. the big theta of the worst case).

thaumasiotes 6y ago

> What irks me is people who use the equal sign as in T(n)=O(n log n), though. Why would a function equal a class? Set membership notation does the job just fine. It's strange but it's fully standard. I would guess it develops from the use in analysis, where o(n) is more common. You derive your formula, it has a term in it that you don't want, you observe that "complicated term's numerator = o(n)", you take your limit, and the term vanishes away. Use of the = sign makes more sense there, because conceptually you're claiming something about the value of the term. (Specifically, that in the limit, it's equal to zero.)