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):
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.