14

Currently, questions on Big-Oh are on-topic on the Programmers main site because they fall under "algorithm and data structure concepts." Does the community feel that these questions should continue to be on-topic, or should we change them to be off-topic?

Arguments for being on-topic

  • These questions are fairly harmless, easy to answer, and there are not a lot of them asked. They do not detract from the focus of the site, and people will ask them anyway.

  • There is no migration path to Computer Science where they are also on-topic, meaning we would need to deal with more moderator flags to migrate or create another open migration path which is additional effort. The status quo is the path of least resistance.

Arguments for being off-topic

  • While sites can and do overlap, Computer Science allows these questions. Being a more academic topic, it may be more appropriate there. Now that CS is out of beta, it is a more permanent target for these questions.

  • There is a canonical wiki locked question What is O(…) and how do I calculate it? which is a dupe target for many Big-Oh questions. New questions do not really ask anything new. Big-Oh is essentially a dead topic as far as new questions.

  • Many if not most of these questions are uninteresting homework questions.

  • 5
    I personally like these questions. Of course, algorithms are on topic here, and Big-O analysis is an integral part of working with algos. However, these questions add little value to Programmers, and the good ones would be a far better fit for CS.SE. So I'm all for updating our scope! Let's be more about software engineering concepts, less about science and coding! – amon Oct 26 '15 at 18:57
  • It would be really nice if there was a VERY comprehensive "how to calculate O() questions. The current one is... lackluster at best (and only 700 views in 3 years? not really useful to others too). – enderland Oct 26 '15 at 19:10
  • @enderland Yep. And I'd be very happy if an excellent self answered question could be written that does a good job of it. That people don't search for it first before tossing a few for loops into the text box is one of our great disappointments. – user40980 Oct 26 '15 at 19:22
  • Would it make sense to update the existing Q/A or write a new one? – user22815 Oct 26 '15 at 19:23
  • @Snowman I'd have a new one, that old question will never get much attention... – enderland Oct 26 '15 at 19:24
  • 2
    I just community wiki'd the target question and answer. I think it's on-topic, but in the current form, it doesn't make sense to duplicate things to it. I think that the big-o tag wiki and the target question both need to be improved to give specific details and examples and such. – Thomas Owens Oct 26 '15 at 19:25
  • 1
    (also, if there's a new one and I see it, I'll be duping it to the original, especially now that it's CW'd). – Thomas Owens Oct 26 '15 at 19:25
  • I can not say anything about the scope of Software Engineering, but from experience I think that most users would be better served on Computer Science. We have more expertise in algorithm analysis, and asymptotic notation. In particular, we have comprehensive reference material on algorithm analysis and asymptotics. (Disclaimer: I'm a mod on Computer Science.) – Raphael Oct 27 '15 at 11:09
  • That is not to say that most of the questions you are getting would not be dupes and be well received over on Computer Science. I don't know what you are getting on average. So my above comment is to be read as a general remark on the two topics. – Raphael Oct 27 '15 at 11:10
  • 2
    @Raphael the first link in the question goes to the "big-o" tag on our main site, which currently has 76 questions which you can browse through if you want. – user22815 Oct 27 '15 at 13:23
10

There are three aspects to these questions that make them... awkward.

All the myriad ways

One of the aspects that students (lets face, its students that ask these questions, more on that later...) ask is that it gets comments back like:

Its different because inner loop is being incremented by loop variable of outer loop.

The people asking these questions have great difficulty in abstracting the solution to one answer to others.

One of my great fears with this is that we'll have the question:

for(i=1;i<=n;++i) {
    x++;
}

What is the Big O?

And then the question:

for(i=1;i<=n;++i) {
  for(j=1;j<=n;++j) {
    x++;
  }
}

What is the Big O?

And then:

while(++i < n) {
    x++;
}

What is the Big O?

And so on. As professors seem to love assigning these homework problems, they keep tweaking the actual implementation and people who don't know how to calculate it in the first place also fail at understanding the abstractions.

Do my homework, or at least check it

These are students that are either asking us to do their homework, or check it. In one exchange on a question I recall:

So is it O(n^2)? -- Student
What makes you think it is O(n^2)? -- Expert
So does that mean its O(n)? -- Student
What makes you think it is O(n)? -- Expert

I really want to say that they either need to do the homework or hand it in. The questions that show no understanding of it, attempt at verifying it themselves, and the like are boring. I do acknowledge that not all people find these questions boring and there are indeed interesting Big O questions, just that the "here's a few nested for loops, what is the Big O?" or "here's a few nested loops, is it O(n^2 log n)?" pasted in a text box are boring.

Poor canonical duplicate

Yep. We have a rather poor canonical duplicate at the moment. It is a community wiki and wiki locked question. That means that it can't be voted on and that means its even harder to find (votes are used in search scoring).


The sum of the parts above is that these questions often fail to material for good answers to be created. It's not that it can't, but the majority of cases are just poor questions asking for poor answers.

I, as a pragmatist want to just say:

Write the code and stick it in a main class or function and count the iterations. Run it for 1, 5, 10, 50, 100, 250, 500, 1000, and 5000 iterations. Toss it in gnuplot or excel or your favorite graphing tool and see what the best fit is.

They're asking people who are drawing on expertise of software design and architecture. While it is useful to know, knowing it beyond "sorting something is O(n log n)" and "contains on an unordered list is O(n)", it isn't something that we run into too often (I run into space complexity problems more often... but we never get asked about that - even if it boils down to the same thing).

We really need a good canonical duplicate question for these if they are on topic here. I'd suggest the tag wiki, but as we know the support for placing information in the tag wiki and being able to find it (or "close as a duplicate of the tag wiki") in the Stack Exchange platform as it stands currently is poor at best.

  • Apparently I don't have it bookmarked, but I remember a M.SE post within the past six months or so where I think it was shog basically agreed that tag wikis are a terrible medium for disseminating information like this because they are so hard to get to for a new user who is likely to ask these poor-quality questions, so nobody actually uses them. – user22815 Oct 28 '15 at 3:36
  • Anyway, you make some good points, but what are you advocating? A better canonical duplicate? Making them off-topic? – user22815 Oct 28 '15 at 3:36
  • 1
    To the part above the line: yes, many poor questions of this form on Computer Science as well. We have better canonical duplicates, imho. To the part below the line: and that's why you should migrate; no offense. (You may also find this an interesting read.) – Raphael Oct 28 '15 at 11:08
  • 1
    @Raphael while there are certainly good candidates to migrate, I am afraid that most of the questions that we get on big O would fall into the "this is not a good question" and the "don't migrate crap" uber rule. Does CS.SE want more questions that it will just close as a dup of the canonical one? That seems like needless bouncing around (that requires a mod on our side). It might also go a ways to figuring out the thing to give examples of big O questions that CS.SE wants (and doesn't want). – user40980 Oct 28 '15 at 13:23
  • @Snowman We should get a nice canonical question that addresses the question from a - dare I say - pragmatic, industry software engineering position (and another answer from the pure CS approach). The answers in this should direct people asking questions that want to go deeper than this to CS.SE. I also really want to avoid having dozens of "what is the big O for this particular nested loop" questions. – user40980 Oct 28 '15 at 13:27
  • @MichaelT I agree that there are too many "but this loop has an extra condition and I don't understand asymptotic complexity!" questions, which makes the question "what to do about this situation" more complex. We either need to (close the crap, migrate the good to CS.SE) || (make off-topic) || (write a canonical non-wiki-locked dupe target). Given our hesitation to create additional open migration targets, and the hesitation to make this off-topic, I believe the choice is clear. – user22815 Oct 28 '15 at 15:45
  • @Raphael I think there would be value in you writing up your own answer and expanding on what you said as well as MichaelT's reply. – user22815 Oct 28 '15 at 15:46
  • 1
    @Snowman I am not sure if we can add CS.SE as a target with the current migration rules. If we can, it would be something for the CS.SE and P.SE mods to say "we want this" to Stack Exchange. It would also be helpful for CS.SE mods to write a "what makes for a good big O migration" so that we don't migrate the questions that would just get duplicated to the canonical answer. It still wouldn't hurt for us to make a canonical answer for this site so that we can duplicate the questions we shouldn't migrate there prior to deleting them. – user40980 Oct 28 '15 at 15:48
  • @MichaelT CS.SE graduated so I am not sure which "migration rules" would make it difficult. I do agree that additional discussion would be warranted that is outside the scope of this meta-question: hence my settling on option 3 (better canonical dupe target). – user22815 Oct 28 '15 at 15:51
  • @Snowman rather than a single big switch graduation, there is now a phased graduation and some things are available at different times... so I'm not exactly sure if we are allowed to have CS.SE as a default target... and even if we are, there is still the "does CS want us to be a site that can migrate to them?" – user40980 Oct 28 '15 at 15:56
  • (I'll point out that there has been resistance from Code Review (another phased migration site) that they didn't want to be a target until they also got updated privilege rep values... again, even if they are eligible from a backend tech, there may still be parts of the graduation that they want to complete before being a target for us). – user40980 Oct 28 '15 at 16:07
8

TL;DR we need a better canonical dupe target.

I advocate for closing the current dupe target and creating a new one.

  • Wiki-locked questions do not allow voting, which interferes with searching and sorting questions and answers. The existing question has few views and is not referenced often enough.

  • Make the new one a regular community wiki question that still allows voting, new answers, etc. but is more welcoming to community edits to improve the content.

  • There is room for additional answers. Each answer can take a different approach. For example, one answer could tackle it from a theoretical, classroom perspective: another from a real world "I need a less bad algorithm to deliver to the customer" approach.

  • By not locking down the ability to vote or add new answers, we can create additional content as needed and ensure that it can rise to the top or sink to the bottom on its own merits.

  • I'd appreciate a ping if you end up pursuing this. The average quality of "big oh" answers on Software Engineering is sub-CS-standard (and it's not close) so I'd like to have a look on what you come up with. Bluntly speaking, I'd rather you send them over if the alternative is to give them bad answers. – Raphael Nov 16 '15 at 10:45
  • @Raphael we did unlock our canonical dupe and we intend to improve it when we get around to it: programmers.stackexchange.com/q/132331 – user22815 Nov 16 '15 at 22:04
4

My concern with eliminating whole classes of questions via Meta is that we may lose an interesting future question based on our experience with bad questions from the past. We say, "New questions do not really ask anything new," and, "Many if not most of these questions are uninteresting homework questions." Those statements are pretty safe. In general, they're true. But does that mean all big-O questions are doomed? Big-O isn't necessarily a simple topic. I can imagine a non-trivial, non-repetitive, non-homework question.

I guess my basic question is: Why another rule? The stinker questions you mention are already sufficiently out-of-bounds because they've been asked before, they're fishing for answers without research, they're trivial, they're unclear, etc.

From what I can tell, eliminating big-O questions may create false positives (false negatives?) while acknowledging that the category may one day give birth to an interesting question doesn't protect the bad questions. Leaving it alone seems to cause less harm.

  • 1
    Looks like we are going the route of keeping them on-topic and improving the canonical dupe target anyway – user22815 Nov 4 '15 at 16:54
3

Let us make Big-Oh questions off-topic here:

  • They are a better fit for CS.SE: good quality questions that are not a duplicate at CS.SE could be flagged for moderator migration.

  • They bring little of value here: many are variations on "what is the Big-Oh of this nested loop?" which gets answered, re-answered, marked as dupe, and closed.

-1

Big-Oh questions should be both off-topic and there should be a better canonical dupe target question.

  • Update the help center to state that a question solely about Big-Oh is off-topic: however, an algorithm question that mentions Big-Oh is fine. The intent being "don't ask your CS Big-Oh homework question here, but feel free to bring it up when discussing an algorithm."

  • Create the new canonical dupe question as per my other answer.

  • Put a warning on the question that questions like it are not good and should not be asked just because this question exists.

  • Mark Big-Oh questions as a duplicate of the new canonical Q/A: a moderator can update existing questions to point to the new canonical dupe, or just delete them.

  • 2
    This is a bit nonsensical. If we're going to declare a subject area off-topic, then we shouldn't have a canonical dupe target for it. If we're going to declare the subject off-topic, then related questions should burn in Trogdor's fire. – GlenH7 Oct 29 '15 at 14:50
  • 1
    @GlenH7 the reason to have a canonical dup (for me) is that its easier to close as a duplicate than try to explain why its off topic. Let me phrase it this way: questions that can be duped to the canonical dup are on topic. Questions that can't are off topic and should be migrated to CS. But in order to (ultimately) delete them here, we need them closed as something. Duplicate works just as well as off topic. – user40980 Oct 29 '15 at 14:56
  • I think the point is moot because there seems to be little desire by the community as a whole to make these questions off-topic anyway. – user22815 Oct 29 '15 at 14:59
  • ... Part of that is based on "we shouldn't migrate crap" (no matter what its topicality). If the question is just going to get migrated and duplicated to CS.SE's canonical duplicate, we should avoid bouncing the asker around from site to site. From the pragmatic industry software engineer standpoint there are unique insights to the big O question that we can provide: It doesn't really matter unless each iteration is significant enough to matter or you have an n that is notable (in which case you have big data... err, problems). Or the "you don't know? profile and measure it" approach. – user40980 Oct 29 '15 at 15:02

You must log in to answer this question.