What is meta? ×
Meta Stack Exchange is where users like you discuss bugs, features, and support issues that affect the software powering all 130 Stack Exchange communities.

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:

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.

share|improve this question
14  
Ever try searching for Θ? I haven't. Because I don't have a Θ key on my keyboard. –  Shog9 May 24 '11 at 19:04
7  
@Shog: You have it now under your Ctrl+V key. Profit! –  BalusC May 24 '11 at 19:09
3  
@Shog: Aw... I feel for you. Have you tried Theta? –  Aryabhatta May 24 '11 at 19:16
7  
The first answer you are talking about is a community wiki. Is it so wrong that you cannot fix it directly? –  yms May 24 '11 at 19:23
9  
Actually the issue you are refering to (abusing big-O notation) is quite common in non-theoretical programming environments. I have never seen a programmer in a production environment saying: "this algorithm will be improved to theta(n*log(n))". So even if the answer is not theoretically accurate, I still believe it has good value, and I definitely do not find it "embarrassing". It would be the case if it was in cstheory.stackexchange.com, but for SO I do not feel it is so dramatically wrong. –  yms May 24 '11 at 19:49
6  
@yms: I am not talking about the nitpicky issue where we could use Theta instead of BigOh. Saying an algorithm is O(n log n) is actually correct, especially when all you are trying to say is that it won't perform worse. In any case, the fact that it is widespread does not make it any less wrong. Also, in production environments, talking about asymptotic behaviour is kind of useless anyway. The number of upvotes to that is embarrassing. Also, just because SO is more programming oriented does not mean we encourage/be indifferent to fudging up the basics, especially when... –  Aryabhatta May 24 '11 at 20:30
5  
@Aryabhatta When we learn about Newton's law of gravity at school we do not learn it with integrals, derivatives etc... We learn it in a more "relaxed" way, which could be seen as "wrong" by experts. IMO this question/answer follows a similar path, given the audience it targets. –  yms May 24 '11 at 20:42
3  
@yms: And what is the definition of BigOh? Isn't it very similar? If it is so advanced, why don't people stop using it altogether? This conversation is turning silly. –  Aryabhatta May 24 '11 at 21:05
3  
Obligatory link to "someone is wrong on the Internet" xkcd comic. –  Adam Davis May 24 '11 at 23:58
3  
@Aryabhatta I'm sorry you're frustrated. I am too. I considered responding to your question, but your responses to good objections raised here are largely "you don't understand the problem." If this were a theoretical computer science site I would heartily agree with you, but stack overflow is largely concerned with the place where the code hits the core, and such technical distinctions are not as important as you suggest they should be. I could complain that string handling on ia64 architecture is misrepresented in every string question, but it's not the place for that level of detail. –  Adam Davis May 25 '11 at 1:47
6  
@Aryabhatta Let me try a different approach. Please link to the questions where the wrong notation leads to programs that won't compile, or will lead to wrong, incorrect, or unexpected program output or operation due to the technically incorrect usage of this topic. There is a difference between popular practical usage and technically correct usage. Where the difference is significant and doesn't impact program operation significantly, stack overflow prefers the popular, practical usage. –  Adam Davis May 25 '11 at 2:13
4  
@Adam: Are you serious? So programming/computer science on StackOverflow is only about getting programs to compile? If you really want to argue that way, I suggest you read this first: meta.stackexchange.com/questions/80023/…. The correct technical discussion of BigOh is very much on-topic on SO and your arguments about compiling programs is quite irrelevant. Answers which talk about that (espcially tagged [big-o] or [algorithm]) are subject to technical correctness of the terms involved. Pardon me if I don't respond. I am really done. –  Aryabhatta May 25 '11 at 2:55
4  
@Aryabhatta "So programming/computer science on StackOverflow is only about getting programs to compile?" No. Answering questions in a clear, useful way without writing a 3,000 word treatise on the subject is the business of Stack Overflow. But Stack Overflow is happy to provide more options: stackoverflow.com/questions/471199/… and stackoverflow.com/questions/3230122/big-oh-vs-big-theta and stackoverflow.com/questions/5464843/proving-big-theta-notation - You probably shouldn't have stopped at the first two results. –  Adam Davis May 25 '11 at 3:22
8  
Hmmm, so if my algorithm has complexity of O(God), does that mean that the result is predetermined? Or does it have free will? –  user147272 May 25 '11 at 7:42
3  
@configurator: You're probably right with "how it's used in practice", and that's a good argument. However, "very close to the truth" is plain wrong. The point is not that the explanation of the real Big-O is more complicated than than the actually given explanation (of Theta); the point is just that "in practice", people often just mean Theta when they say Big-O (which is OK with me; people often use wrong nomenclature). –  Hendrik Vogt May 25 '11 at 13:24

5 Answers 5

up vote 23 down vote accepted

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.

share|improve this answer
8  
And that is quite futile, IMO (for this particular problem). Hence the reason for posting here. –  Aryabhatta May 24 '11 at 19:12
    
btw, I already downvoted and left a comment to the 900+ answer (which is lost because of the flood of comments already)... –  Aryabhatta May 24 '11 at 19:20
3  
@Aryabhatta Yeah, with the high-voted answer this can be difficult. I second the suggestion to edit the wiki if the information is really egregiously wrong. You asked what avenues exist for preventing misinformation... those are it: downvote, comment, edit. –  Anna Lear May 24 '11 at 22:44
    
Yeah, looks like it. Hopefully there is more awareness :-) –  Aryabhatta May 24 '11 at 23:59

<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>

share|improve this answer
2  
Red hammers are better because they cut through tree trunks faster!!! –  Donal Fellows May 24 '11 at 23:00
4  
More seriously, I've seen people arguing over the value of constant k to use in O(kN) for a particular algorithm. Really. I'm actually proud that I just left them alone instead of telling them what a pair of nitwits they were. –  Donal Fellows May 24 '11 at 23:04
    
@Donal: +1 for being the better person. –  MrHen May 25 '11 at 15:24
2  
Big-O is a tool than can be applied correctly or incorrectly. It doesn't give you all the information about an algorithm, only some info about how well the problem scales, which is potentially very useful. Disregarding Big-O completely is as much a mistake as thinking it's the only relevant statistic. –  Justin Morgan May 25 '11 at 15:34
    
Relevant: codinghorror.com/blog/2007/09/… –  Justin Morgan May 25 '11 at 15:36

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

share|improve this answer
1  
+1 for pragmatism. –  NickC May 24 '11 at 23:30
4  
And you are missing the point of my post :-) Absence of formalilty does not mean you can be incorrect. When asked about BigOh, you explain Theta, scatter your answer with a mixup with Omega and never really explain what BigOh is. You are just setting up with 8 year old to be highly confused :-) Besides, what does in practice really mean? The fact that the mistake is widespread does not automatically make it in practice. –  Aryabhatta May 24 '11 at 23:32
6  
@Aryabhatta What you have been pejoratively terming incorrect and misinformation is actually an approximation. The beginning stages of learning are absolutely filled to the rafters with approximations. The argument "you are just setting up the beginner to be confused" is a classic among pedants. Sometimes I have to wonder, were these types born with such an advanced knowledge that they literally cannot empathize with those beginners that they claim to be so concerned about? –  NickC May 24 '11 at 23:48
6  
@Renesis: Calling it pedantry is just ridiculous. Having incorrect (or in your words "approximate") answers on a site specifically meant for Q&A ought to be voted down, when there are perfectly good ways to explain the concepts correctly that even laymen can understand. What if some beginner coder came here and the highly voted answer was riddled with basic programming mistakes. Calling those out would be pedantry too? Just because you are unfamiliar with some concept and consider it theoretical does not mean insisting correctness about it is pedantry. Pardon me if I don't respond to you. –  Aryabhatta May 24 '11 at 23:57
3  
@Aryabhatta you are free to vote it down, and given how you feel, you absolutely should. And you've done well to comment, as well. However, you've come here to appeal to some higher power to get a resolution your way. Sorry, that's not how it works, by design. "highly voted answer [...] riddled with basic programming mistakes" - that's a bit of a constructed scenario, don't you think? Also, I don't recall asserting anything here to be theoretical. –  NickC May 25 '11 at 0:00
2  
@Aryabhatta If a programmers with some university or technical degree takes a book "programming for children" and assumes that everything there is formal and accurated, it will be his own (ir)responsability. I think what makes the difference in this case is the title of the question, I would never expect a completely accurated answer under such title. –  yms May 25 '11 at 0:03
1  
@yms: Absence of formality does not mean you can be blatantly incorrect (especially on a Q&A site). There are plenty of ways to correctly explain BigOh/Theta/Omega to laymen/children/etc. –  Aryabhatta May 25 '11 at 0:22
1  
@Aryabhatta Well, I have a few books on the topic on at least 3 languages, and I have not been lucky enough to find such a clear explanation... I have to say that I do like the 900+ answer. I feel it is like when I was told that 1-4 "was not defined" in primary school. It was wrong, but we grow up to learn that later.I look forward to the modifications you will do if you finally decide to do it. –  yms May 25 '11 at 0:30
    
@yms: I don't think I am going to make any edits. I have already wasted enough time on this, and frankly the attitude of some folk has really put me off trying to help. The 900+ answer is a good explanation, but of the wrong thing! Anyway... –  Aryabhatta May 25 '11 at 0:37
3  
@Aryabhatta Perhaps you could make a small edit to the post to explain somewhere at the beginning of it what it's describing? That way you don't have to make extensive edits and you still convey the information you want. –  Anna Lear May 25 '11 at 0:46
    
@Anna: Nah, I think I will let it pass. People can choose to remain ignorant/spread it, I don't care anymore. Thank you for the time you have spent on this thread. –  Aryabhatta May 25 '11 at 1:59
2  
@Aryabhatta: I just added Jon Skeet's disclaimer to the accepted answer. –  Hendrik Vogt May 25 '11 at 14:28
1  
@Renesis is correct. Using Theta as an explanation for Big-Oh is an incredibly useful approximation for programmers. –  Adam Rackis May 25 '11 at 18:31
1  
My take is that formal accuracy is not the only criterion for an answer being good. Indeed, the true criterion has to be whether it causes the questioner to gain understanding that is closer to reality: a simplified approximation that can be understood is better than the full details if the latter is beyond what the other side can grasp. (Ideally the gap between the two is small, but when the task is explaining to children it's expected that many details will be left out.) –  Donal Fellows May 27 '11 at 12:40

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.

share|improve this answer
3  
This is an excellent suggestion. The wikified answer can simply have "This answer is useful but inaccurate. Please see link-to-other-question for details and technical discussion." added to the top. This will take all of two minutes. –  Josh Caswell May 24 '11 at 20:55
2  
@Josh: I am reluctant to make such edits. Inspite of the how long it takes. –  Aryabhatta May 24 '11 at 20:58
2  
@Aryabhatta: Why? The answer is Community Wiki. –  Josh Caswell May 24 '11 at 20:59
4  
@Josh: I consider it very bad etiquette to call out that an answer is wrong by actually editing that answer itself! I think we should reserve answer edits (by someone other than OP) for minor corrections. (If I recall correctly, Jeff Atwood stated the same opinion on one of the meta threads). –  Aryabhatta May 24 '11 at 21:02
5  
@Aryabhatta: I agree that it is rude generally. This answer, however, is CW and has already been edited by other users than the original answerer. I also am not suggesting that you say that the answer is simply wrong, but that you provide additional information to make it more accurate. That would be an excellent reason to edit a CW post, especially one with such visibility. –  Josh Caswell May 24 '11 at 21:07
    
@Josh: Also, it is a very likely possibility that one of the 900+ people will just roll back those changes, especially given the kind of edit. Btw, adding that link won't make the answer more accurate. The major portion would still be wrong and it would probably make that answer kind of useless. –  Aryabhatta May 24 '11 at 21:09
4  
@Aryabhatta: I'm fairly certain that if you edit the answer to a correct state and properly cite sources, the main reaction would be "Whoa, I didn't realize!" rather than "Well, that's obviously wrong! /rollback". Don't be so pessimistic. :) –  adamjford May 24 '11 at 21:21
3  
@adam: Visiting SO and looking at all that happens (especially in the [algorithm] tag) has made me more pessimistic than usual! :-) Really, though, I don't really like to make such edits. –  Aryabhatta May 24 '11 at 21:28
8  
Substantially editing a 900 votes answer feels wrong, because then suddenly those 900 upvotes are associated with different content than the one the people originally voted on. –  sth May 24 '11 at 21:28
4  
Identify the problem and fix it. I don't care what 900 people think, if what they think is wrong. @Aryabhatta states he has found a grievous problem. One which cannot stand without it being fixed. Therefore he should fix it. However, if he merely takes issue with the post, he should downvote it. –  user7116 May 24 '11 at 21:50
1  
@six: How many such posts do you expect me to just fix it? –  Aryabhatta May 24 '11 at 22:07
4  
@Aryabhatta: Sixletter is right on. This is what it comes down to: you think there's a problem. You have the means to fix the problem, namely, editing the post to add more information. (Not to just wipe out what's there -- but to make it better.) If you say "this problem is super-important" but also "it would take me too much time to fix it", then I believe you have a contradiction, and you should either reconsider or just let it go. –  Josh Caswell May 24 '11 at 22:07
3  
If you're not going to fix the posts, who will? I'd never seen the post you referred to even with 900+ posts. I have a pretty narrow tag filter to ensure I don't see those sort of posts (read: unhelpful). The point I'm making is when you find a problem, fix it. SO has given you the tools: downvote, edit, flag for attention, comment, answer. –  user7116 May 24 '11 at 22:51
2  
@Aryabhatta: Okay, I will address your meta post directly. Your question says: <quote>Is there a way we can somehow refer readers of some of the mistaken questions/answers to 471199?</quote> The answer is: Yes, edit the answer to include a link. Other question: <quote>Any thoughts on SO helping prevent the spread of this misinformation?</quote> Answer: Yes, when you come across posts that you think are mistaken, downvote, leave a comment, or in the case of CW posts, edit to make it better. It's also possible to put a bounty on a question, and add your own answer. –  Josh Caswell May 24 '11 at 23:04
1  
@six: I am hoping to find a better solution than just fixing up all the existing posts (which i reckon will be in the hundreds, if not thousands!). Also I have turned to meta only after using the existing tools like downvotes/comments/editing posts. I don't think flagging will help, though. In the worst case, the posts will have to be edited, of course. –  Aryabhatta May 24 '11 at 23:26

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.

share|improve this answer
2  
Thank you for your answer. I admit, I didn't read the whole of the third answer (hence my usage of the word 'seems'). The fact that it (BigOh/Omega/Theta misuse) is prevalent makes people think it is OK (justified with silly(IMO) terms like 'practical', 'pragmatic') is just adding to the misinformation. StackOverflow is a good avenue to dispel that. But I guess, change for something so ingrained is hard. –  Aryabhatta May 25 '11 at 15:13
1  
I totally agree with you that the misuse should be pointed out (as Jon Skeet did). As you saw, I added his disclaimer to the 700+ answer; I think that's all one can do. –  Hendrik Vogt May 25 '11 at 15:19
    
Agree, In fact that is why I accepted Anna's answer. I guess posting here did raise some awareness, unfortunately offending some in the process. –  Aryabhatta May 25 '11 at 15:24

You must log in to answer this question.