13
\$\begingroup\$

Here is an example of a question that asks for a big-O analysis of a function (to count the number of ways to make change): What is the run time of this algorithm?

Here is my algorithm

I want to know what the run time of this algorithm is. I initially thought it would be \$O(4^n)\$ since each call makes up to 4 recursive calls.

But, for an amt of 10, that would be 1,048,576 and that seems insane. How do I go about finding out what the big \$O\$ of this is? (I'd appreciate the method to approach the answer rather than the answer directly)

We have many questions where complexity is a concern, and we even have a tag for it. Also, we have questions, for which answers often give a diagnosis that the algorithm scales poorly.

But this question seems to be purely about how to determine the complexity of some given code, with no interest in improving the code. Seeking an explanation of how code works is explicitly off-topic.

  1. Is this question off-topic for Code Review, by the current rules? If so, do you believe that the prohibition is justified?
  2. There are many questions that are currently considered on-topic. Where do we draw the line?
  3. Could this lead to a migration hot potato with Stack Overflow, where Code Review rules it off-topic because it's not seeking a critique, but Stack Overflow wants to send it to Code Review because it's primarily a discussion of the author's code? What guidance should we give to the author to help resolve jurisdictional issues?
\$\endgroup\$
  • \$\begingroup\$ Are we talking about this question in particular or questions like this in general? \$\endgroup\$ – Simon Forsberg Jul 28 '17 at 14:26
  • 1
    \$\begingroup\$ @SimonForsberg Questions like this in general. I have been concerned about this issue for some time now; this specific question just seems to be a particularly problematic example. \$\endgroup\$ – 200_success Jul 28 '17 at 14:29
  • 3
    \$\begingroup\$ On cs.stackexchange.com they close all these "easy" algorithm analysis questions (most of which are homework exercises) as duplicates of this question. \$\endgroup\$ – Gareth Rees Jul 28 '17 at 17:02
  • \$\begingroup\$ Another recent example of question that is purely about complexity analysis of a sorting algorithm. \$\endgroup\$ – 200_success Jul 28 '17 at 18:00
  • \$\begingroup\$ @200_success For the example in your question, I feel that the author is misunderstanding the purpose of Big-O notation, or complexity analysis, and as such I think it would be off-topic as the author isn't asking what they think they're asking. \$\endgroup\$ – 410_Gone Jul 28 '17 at 18:06
  • \$\begingroup\$ @200_success And in regard to the question you just commented about, I feel that one is closer to dark-gray than light-gray, as it asks "what class is this" and "its complexity", without any other concern. \$\endgroup\$ – 410_Gone Jul 28 '17 at 18:07
  • \$\begingroup\$ @EBrown "Unclear what you are asking" is not the same thing as "off-topic". \$\endgroup\$ – Simon Forsberg Jul 28 '17 at 19:13
  • \$\begingroup\$ @SimonForsberg Whatever, semantics. You know what I meant and that comment is entirely unconstructive. \$\endgroup\$ – 410_Gone Jul 28 '17 at 19:14
  • \$\begingroup\$ Sorry but I thought it was an important distinction as we are discussing whether or not such questions are off-topic. \$\endgroup\$ – Simon Forsberg Jul 28 '17 at 19:16
  • \$\begingroup\$ Would the question be better off on the Computer Science Stack Exchange? \$\endgroup\$ – user1118321 Jul 30 '17 at 2:50
  • \$\begingroup\$ @user1118321 "Better fit elsewhere" is not a consideration for determining whether a question is within the scope of Code Review. Each site decides its own rules, and there may or may not be overlap as a result. For your information, though, CS generally closes requests for complexity analysis as duplicates of this canonical question — as mentioned in a previous comment. \$\endgroup\$ – 200_success Jul 30 '17 at 6:57
6
\$\begingroup\$

Let's take a look at the help:

I'm confused! What questions are on-topic for this site?

Simply ask yourself the following questions. To be on-topic the answer must be "yes" to all questions:

  • Is code included directly in my question? (See Make sure you include your code in your question below.)
  • Am I an owner or maintainer of the code?
  • Is it actual code from a project rather than pseudo-code or example code?
  • Do I want the code to be good code? (i.e. not code-golfing, obfuscation, or similar)
  • To the best of my knowledge, does the code work as intended?
  • Do I want feedback about any or all facets of the code?

If you answered "yes" to all the above questions, your question is on-topic for Code Review.

To answer your first question: yes, it's off-topic. This particular question doesn't appear to be interested in feedback about any or all facets of the code like you mentioned.

I won't go into whether prohibition is justified. But please consider whether we would want to handle multiple questions like this each day.

As to your third question, I don't think Stack Overflow likes such questions any better than we do. Migrating questions like this wouldn't do any site (and the OP) any good.

\$\endgroup\$
  • 4
    \$\begingroup\$ I dislike that part of our help, partially because very often we're happy with them just wanting to learn something. If an OP asks "How can I speed up this code?" we're not telling them "Sorry, you don't want to know if your variable names are good, your question is off-topic! BAM! HAMMERED!" and I don't think we should treat questions like that. Slightly related: Can we ask reviewers to not focus about something? \$\endgroup\$ – Simon Forsberg Jul 28 '17 at 7:17
  • \$\begingroup\$ @SimonForsberg That's a discussion I'm specifically avoiding here, but feel free to write your own answer and go at it anyway :-). Within the current scope, the referred question is off-topic. If we want to modify our scope, we should do so very carefully. \$\endgroup\$ – Mast Jul 28 '17 at 7:31
  • 4
    \$\begingroup\$ I agree with Simon. This last bullet point alone should not be strong enough a reason to close. In practice, despite OP's apparent ignorance, when the content of the question is interesting enough, and there are interesting lessons to teach about it, reviewers force-feed their recommendation to the OP anyway, and I think that's fine and better than closing. But yes this is a different discussion from the main question here. And I agree it's off-topic, just not 100% about the reasoning. \$\endgroup\$ – Stop ongoing harm to Monica Jul 28 '17 at 7:33
  • 4
    \$\begingroup\$ @janos agreed... IMO force-feeding a review to an uninterested OP is basically lowering the bar of post quality on the site. \$\endgroup\$ – Mathieu Guindon Jul 28 '17 at 17:23
  • \$\begingroup\$ @Mat'sMug That's the thing, I think 100% of the OP's that ask about time complexity are interested in optimizing the algorithm. Somehow I am reminded about Does the plain-English part of a question even matter? \$\endgroup\$ – Simon Forsberg Jul 28 '17 at 19:03
4
\$\begingroup\$

Upon reading the question and the linked question, I would boil my decision down the the following bit:

I want to know what the run time of this algorithm is. I initially thought it would be \$O(4^n)\$ since each call makes up to 4 recursive calls.

But, for an amt of 10, that would be 1,048,576 and that seems insane. How do I go about finding out what the big \$O\$ of this is? (I'd appreciate the method to approach the answer rather than the answer directly)

This tells me that the OP doesn't understand what Big-O notation is, or what we use it for: "for an amt of 10, that would be 1,048,576" - this is a blatant misunderstanding that, admittedly, I had when I first starting working with Big-O notation, but the question no longer makes sense in that situation. Instead, we're left with a pile of code, and a very confused OP.

I would vote this UWYA, for the reasoning that it really is unclear. I would like clarification on at least one of the following before considering it answerable:

  1. Why do you care what the Big-O notation is, what do you intend to do with that information?
  2. What made you think it's \$O(4^n)\$, how did you come to that conclusion?
  3. What makes you think that 1,048,576 calls seems insane, why does that sound unreasonable?

The question is not about the code anymore, it's more speculative. Thus, as it stands it's 'unclear what you're asking'.


You posted a comment with this question, which I think lends itself to a similar but not identical issue.

... I did not compare this with existing sorting algorithms. Can someone tell me what class of sorting algorithm this is and it's complexity? ...

This is one of those times that I feel a DV+CV is warranted. This entire question screams 'I did not at all do any research and I expect all of you to do it for me'. The OP, in this case, seems entirely disinterested in the idea of the code itself, but only cares about the algorithm, and in particular, the complexity of the algorithm.

In this case, I boil this issue down to a request for code explanation (which we are all pretty much in agreement is off-topic). At least the first example showed that the OP did some research effort (however right or wrong it may be), in this case the OP did absolutely no research effort, and proudly proclaims as such.

Bottom line on this one: explanation of code has always been off-topic, and asking us to explain the run-time complexity even more so because it implies an explanation of code first.

\$\endgroup\$
  • 1
    \$\begingroup\$ A close-vote should not be used as a "super down-vote". Your second example here also reminds me about How much research effort do we expect? \$\endgroup\$ – Simon Forsberg Jul 28 '17 at 19:10
  • 1
    \$\begingroup\$ @SimonForsberg I'm not using a CV as a 'super DV', but am using it instead as it was intended (weird how that works). The first question I did not CV, by the way (nor DV), the second I DV'd for 'no research effort at all', and CV'd for 'requesting explanation of complexity of the code'. \$\endgroup\$ – 410_Gone Jul 28 '17 at 19:13
  • \$\begingroup\$ The OP's question seemed clear to me. If you just look at the recursive structure of the function, then each call results in up to 4 recursive calls on smaller values of \$n\$, and so a naïve bound on the runtime is \$O(4^n)\$. But it seems very unlikely that this bound is tight — when called with \$n=10\$ the function clearly doesn't make anything like \$4^{10}\$ calls. So the OP was pretty sure that a tighter bound could be established, but couldn't figure out how to go about finding or proving such a bound. \$\endgroup\$ – Gareth Rees Jul 28 '17 at 22:47
  • \$\begingroup\$ @GarethRees Write up an answer if you feel that way, but the OP's lack of understanding (and the nature of the question itself) leaves a hell of a lot up to interpretation, and I don't like assuming for the sake of assumption. To be completely honest, I don't really care anymore in any direction, just tried to write an opinion on why I'd rather not go blindly accepting any 'Complexity' question as on-topic. \$\endgroup\$ – 410_Gone Jul 28 '17 at 22:52
  • \$\begingroup\$ I did write an answer! \$\endgroup\$ – Gareth Rees Jul 28 '17 at 22:54
  • 2
    \$\begingroup\$ @GarethRees I meant on this question, but that just goes to further prove my point: we seem to really like shoving words and ideas into the OP's mouth. \$\endgroup\$ – 410_Gone Jul 28 '17 at 22:55
2
\$\begingroup\$

Tags don't make questions on-topic.

Remove the tag from the question. Would you argue that it's still on-topic for Code Review? No-where does the question ask for a review of the code, and it's asked in such a way that it reads to me that it doesn't want a review of the code.

This question breaks only the first section of What types of questions should I avoid asking?.

First, make sure that your question is on-topic for this site. In short, questions seeking open-ended feedback on real working code that you own or maintain are on-topic for Code Review.

Since it's breaking the premise of this site, the reason it's off-topic isn't in explicitly in our close reasons.


There is overlap between the tags , , and . This normally is due to improving complexity is the best way to improve overall performance. And so an answerer is likely to mention the slow codes complexity, such as \$O(n^3)\$, and how to improve it to something more reasonable, such as \$O(n)\$. However and are about improving raw time, so micro optimizations can come into play. However complexity is about the overall theoretical performance, which doesn't change from language to language.


To answer your questions:

  1. Is this question off-topic for Code Review, by the current rules? If so, do you believe that the prohibition is justified?

    Yes, as it's not asking for a review of the code.
    Yes, as we're a code reviewing site, with the aim of improving code. We don't leave bad code being bad code, as people just want to know the complexity of their code. And reviewing the code is a waste of the answerers time.

  2. There are many complexity questions that are currently considered on-topic. Where do we draw the line?

    I drawn the line at whether the question is asking for a code review. Heck this would be off-topic just from the first paragraph of our tour:

    We're working together to improve the skills of programmers worldwide by taking working code and making it better.

  3. Could this lead to a migration hot potato with Stack Overflow, where Code Review rules it off-topic because it's not seeking a critique, but Stack Overflow wants to send it to Code Review because it's primarily a discussion of the author's code? What guidance should we give to the author to help resolve jurisdictional issues?

    Possibly, however I personally don't remember anyone advising one of these questions to Code Review. If they did, then I'd simply state that the question is not asking for a review of the code, and so is not on-topic on Code Review. Get an upvote or two on your comment and the asker normally doesn't post on Code Review.

    However, I'd rather be reactive to this issue, as whilst bad suggestions to Code Review on Stack Overflow are common. I don't think this specific reason is a problem.

\$\endgroup\$
  • \$\begingroup\$ "questions seeking open-ended feedback on real working code that you own or maintain are on-topic for Code Review." covers all our on-topic and off-topic reasons, it's not just "a premise". We have a specific close reason for non-working code, and yet that is also in "the premise"? \$\endgroup\$ – Simon Forsberg Jul 28 '17 at 14:28
  • \$\begingroup\$ @SimonForsberg I must have worded that poorly. My point is it goes contrary to the "premise", but is not explicitly forbidden in any of our close reasons AFAIK. \$\endgroup\$ – Peilonrayz Jul 28 '17 at 14:34
0
\$\begingroup\$

(Note that this answer addresses question like this in general rather than this specific question)

Let's think for a minute.

Why does anyone want to know their code complexity?

What is the difference between "What is the time complexity of this code?" and "How well does this code scale?". There is no difference really, as time complexity is exactly about how well the code scales.

What is the difference between "How well does this code scale?" and "How good is this code?". Time and Memory complexity is one part of how good the code is.

What is the difference between "How well does this code scale?" and "Can I make this code faster?". If the answer to your code scale is that it scales horribly, would you say "Okay, thanks" and be happy with that? Unlikely. The reason for the question in the first place is that you are interested in the performance of the code and you are thinking about if it can be done faster.

Inside every "What is the time/memory complexity of this code?" I think there is a "How good is this code?" and a "Can I make this better?"

I think this is on-topic.

\$\endgroup\$
  • 3
    \$\begingroup\$ I would upvote, but I think this is [partially, at least] putting words in OP's mouth. Many SE/SO newcomers ask poorly worded yes/no questions that IMO should be closed. We have a bar for question quality, and the bar must be at a given height to ensure quality posts. Assuming OP's intentions to keep the question open, lowers that bar in my opinion. (not my downvote) \$\endgroup\$ – Mathieu Guindon Jul 28 '17 at 17:21
  • 1
    \$\begingroup\$ @Mat'sMug I asked the OP in this case and what do you know. "If there is a better way to do it, then yes, absolutely!" \$\endgroup\$ – Simon Forsberg Jul 28 '17 at 18:59
  • \$\begingroup\$ @Mat'sMug Low quality posts is a different thing than off-topic. If it is low quality, downvote (and preferably comment). If it is off-topic, closevote. For low quality posts I refer to the guide I wrote for asking good CR questions. So far I haven't encountered a single person that doesn't also want to know if there is a better way to do it. I haven't put any words in their mouth, I've just asked them about it. \$\endgroup\$ – Simon Forsberg Aug 4 '17 at 9:39
-3
\$\begingroup\$
  1. Is this question off-topic for Code Review, by the current rules? If so, do you believe that the prohibition is justified?

    It's not explicitly off-topic, no. The only reason it can be considered off-topic is because the OP doesn't explicitly say that they are interested in "Any and all aspects of the code". But there are a lot of question that doesn't say that, but instead say something like "Can I improve the performance of this code?". Is that to be considered off-topic too? No? Why not? If we would start treating such questions differently, I expect us to have more off-topic questions than on-topic.

  2. There are many complexity questions that are currently considered on-topic. Where do we draw the line?

    Where to draw the line exactly is impossible for me to answer. Too many variables to consider. I'm gonna have to say pass on this question.

  3. Could this lead to a migration hot potato with Stack Overflow, where Code Review rules it off-topic because it's not seeking a critique, but Stack Overflow wants to send it to Code Review because it's primarily a discussion of the author's code? What guidance should we give to the author to help resolve jurisdictional issues?

    Yes, it definitely will lead to a hot potato. It's taken a long time to make Stack Overflow understand our current scope (Only working code, no example code), every change we make to our scope will make us have to teach them again. I don't say that we never again should change our scope, absolutely not. But when we do, we should think about the reason for why we are doing so.

    If someone just asks "What is the complexity of this code"? Then please, ask them if they want to also want to know if it is possible to make the code faster. So far I haven't found anyone who says "No, I just want to know the complexity." to that question. When in doubt, ask for clarification in a comment. That's what comments are for.

\$\endgroup\$
  • 3
    \$\begingroup\$ I disagree with 1, as it read as they didn't want a review. Where other questions that do leave out the 'can I have a code review', read as they do actually want a code review. And as we know, the plain-English part of a question does matter. I agree with the last paragraph to 3, should swiftly move it from the grey zone to either the black or white, depending on their response to "ask them if they want to also want to know if it is possible to make the code faster". \$\endgroup\$ – Peilonrayz Aug 7 '17 at 11:33
  • \$\begingroup\$ @Peilonrayz Regarding 3: Exactly. No need for us to decide if all such questions is on-topic or off-topic if we can let them do it for us. \$\endgroup\$ – Simon Forsberg Aug 8 '17 at 17:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .