O(God), why are we helping spread misinformation?

Question

There is a common misuse prevalent, of using BigOh, whenever we mean Theta, or in some cases, Omega. (In fact, the misuse is so prevalent, that I even expect many people to go WTF? after reading this.)

Take a look at some of the highly voted answers here ( I stopped looking after these two):

• What is a plain English explanation of "Big O" notation?
• Big-O for Eight Year Olds?

The accepted answer to the first one is quite blatant as it starts off with a wrong definition, abuses Theta (and in some cases Omega) with BigOh. The explanation about the behaviour of various functions, though nice, is completely irrelevant to what BigOh really means and how to correctly use it.

One could try downvoting it + leaving a comment/and/or adding one's own answer, but it has got an embarrassing 900+ votes (and a flood of comments) and any effort directed towards that question would likely be futile.

Fortunately, there is one question (and it's accepted answer) which seems to have gotten it right:

• What is the difference between Θ(n) and O(n)? (Question # 471199)

Is there a way we can somehow refer readers of some of the mistaken questions/answers to 471199? We could add a link to this question in the tag-wiki, but who reads those?

Any thoughts on SO helping prevent the spread of this misinformation?

Note: Even though I specifically called out the 900+ post, that is just one of the many posts that need dealing with.

Answer 1

The best way would be to downvote the wrong answers and leave comments. You can add a link to the correct explanation of the differences to your comment.

You can also post an answer of your own that contains accurate and valid information.

Beyond that, there's not much you can do.

Answer 2

<rant>
Personally, if we're really going to discuss this, I feel that most people that uses these terms don't use them correctly at all, and not because they get it wrong in terms of your definition, but mostly because they get it wrong that they should use those terms in the first place.

For instance, it's not uncommon for people to get bogged down into discussion about whether one sort algorithm has a better O(...) (any variant of the letter O for the various terms) than some other sorting algorithm, and then blatantly forgetting that they're only going to sort at most 100 items.

In this case, it might well be that your algorithm of choice, though it has a better O(...) than the alternative, has a much higher constant overhead induced, which means that while you're going to perform fewer operations, each operation is more costly.

And then they use those terms about their algorithms to discuss actual performance with actual data.

Now, don't get me wrong, I feel it's helpful to know the behavior of algorithms in respect to the size of the input, is it recursive in some way, nested loops, cross-products, whatnot, but sometimes the only way to figure out if one algorithm is performing better than another for your specific case is to just implement both and profile them.

And that's why I don't like Big-Oh notation, as only a few select people (and I'm not one of them) is really qualified to be talking about it, and most of the rest shouldn't be talking about it or using it in the first place.

It's a bit like arguing whether a red hammer is better than a green hammer, when in reality you need a saw.
</rant>

Answer 3

To my eyes, you're missing the point of those two questions, neither of which actually desired a formal mathematical definition of the notation, but rather an explanation of how the notation is used in practice. The plain English explanation does not need a detailed explanation of the various types of asymptotic complexity behaviors, but rather what this means, and I shudder to think how to teach 8-year olds about it. Remember, it is very important that a question be answered in a way that the questioner can comprehend. Once they've got the basic concepts, they venture further down the rabbit hole towards full understanding.

Also, I wouldn't sweat algorithms with Θ(f(N)) complexity being described as having O(f(N)) complexity; after all, the former strongly implies the latter (and Ω(f(N)) too, but that's beside the point).

Answer 4

The first one you linked to is a Community Wiki. Delete the incorrect parts and replace them with the correct ones. Optionally link to the better question you found.

Sometimes a wiki entry needs a drastic edit.

Answer 5

Let me first say: Of course you're right that most of those answers explain Theta and not Big-O, although the question was about Big-O. But let me highlight two points that I find important.

• It's not that the answers are wrong, it's just that they explain a thing that is wrongly called Big-O by many. But this is a general phenomenon, terminology that in theory should be used for something specific is used for something almost, but not quite, entirely unlike the Real Thing.

• The first two questions you link to just ask for an explanation of Big-O; the third one explicitly asks for a comparison between Big-O and Theta, so of course a good answer to the third question has to use correct terminology.

At the time of posting this answer, I actually liked the accepted answers to the first two questions better than the accepted answer to the third question: With the first two, it's clear from the style that they just want you to get the idea (of Theta, which they wrongly call Big-O, but so what). The third is on a completely different level, giving precise definitions, but nevertheless it contained at least two distinct mathematical errors. Isn't this worse than incorrect usage of terminology? (Nothing against the poster of that otherwise very nice answer, noone is immune to such errors, and they were not beginners mistakes.)

^{Full disclosure: I'm a mathematician.}