Are requests to analyze the complexity of code on-topic?

Question

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 complexity tag for it. Also, we have time-limit-exceeded 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 complexity 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?

Answer 1

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.

Answer 2

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.

Answer 3

Tags don't make questions on-topic.

Remove the complexity 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 complexity, time-limit-exceeded, and performance. 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 time-limit-exceeded and performance 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 draw the line at questions not 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.

Answer 4

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

Answer 5

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.