3

Is there anything that can calculate the Big-O notation of a function? While learning about Big-O, it is implied that it is pretty trivial to do in your head once you know the basic rules, however if that were true, I would expect this functionality to be embedded in various IDEs. I have not seen any tool like this.

Is this something that can be easily interpreted via software, or does this require context that is only available to the developer?

Improve this question
12
  • 2
    You could probably estimate it by measuring the time it takes for the first few iterations of n to execute, assuming that the algorithm is not O(ludicrous). Commented Jan 30, 2020 at 21:15
  • 1
    @RobertHarvey: That would require an assumption that processing performance does not vary during the test, because otherwise measuring the time is reasonably imprecise. Commented Jan 31, 2020 at 10:17
  • 3
    @JörgWMittag: Taken from the comments on a comment link on on of the answers here: "The halting problem doesn't say we can never do it. It says that there are programs for which it cannot be done." What you're arguing is the equivalent of saying that if you can't divide by zero, you therefore cannot divide by any number. Even if OP's suggested tool would only be able to handle some but not all cases, that still means it's not impossible as your answer is claiming. Commented Jan 31, 2020 at 10:21
  • 3
    @JörgWMittag: Are you able to divide a number by another number? According to your posted answer, you should be answering "no, this is impossible", which is a clearly nonsensical answer. You can divide a number by another number, but there are some exceptions where it cannot be done (dividing by zero). This is not inherently an all or nothing question - if a reasonable line can be drawn where sometimes it can't be done, that is not the same as stating it is impossible. Commented Jan 31, 2020 at 10:32
  • 2
    @JörgWMittag: "there are also infinitely many functions for which it is not possible" And just to extend the analogy, there are infinitely many numbers which cannot be divided by zero either. I agree completely with your assertion that it can never be guaranteed, but I wholeheartedly disagree with labeling this as "outright impossible" instead of "partially (im)possible" Commented Jan 31, 2020 at 10:38

3 Answers 3

Reset to default
1

As far as I remember, each algorithm for which you know a theoretical complexity has its size-to-time plot, which means that for a small data samples you can get a higher execution time.

Most of current IDEs support performance unit tests.
You could generate data samples with different random sizes and pass it to you unit test.
An IDE will gather the statistics for you.
Then you could look at a size-to-time plot and check if your assumptions about an algorithm's complexity were right.

Improve this answer
0

Big-O notation is methodical and depends purely on the control flow in your code so it's definitely doable but not exactly easy..

It would probably be best to let the compilers do the initial heavy lifting and just do this by analyzing the control operations in the compiled bytecode. Also, studying compilers might help with this, such as learning how they perform code reachability analysis.

Basically (as far as I know), every instruction is constant time complexity except for backwards branches.

So if you come across any backwards branch instruction you'd need to store contextual data, especially about that loop's exit condition, and determine the Big-O of that loop. Then multiply its complexity by the complexity of instructions contained within it, which could be other method calls or backward branches that you'd need to recursively analyze.

As for special context not known to the compiler: Big-O wouldn't care since it assumes the worst case, but you could always let your analyzer report additional things about the complexity of the method, assuming you make it smart enough.

Improve this answer
7
  • "Definitely doable" - you may want to reconsider your claim: stackoverflow.com/questions/480775/… Commented Jan 31, 2020 at 0:06
  • 1
    @whatsisname: From the comment on the top answer in your link: "The halting problem doesn't say we can never do it. It says that there are programs for which it cannot be done." OP's question does not necessitate a 100% hit rate. If some functions cannot be analyzed, so be it. But you're implying that if some functions can be analyzed, then we can't analyze any functions, which is does not logically follow. Commented Jan 31, 2020 at 10:13
  • "Also, studying compilers might help with this, such as learning how they perform code reachability analysis." - Unfortunately, Code Reachability Analysis is … you guessed it … equivalent to solving the Halting Problem. Commented Jan 31, 2020 at 12:17
  • @whatsisname Sorry, I see how that statement could be misunderstood. I didn't mean that you can program something which can solve the complexity of every method; It was a response to OP's question that, yes, you can write a program for an IDE which can solve the complexity of methods (maybe not every method though..) and, no, you don't need special context. I am aware of the Halting Problem which is a good part of why I included a link about reachability analysis. Commented Feb 3, 2020 at 19:50
  • 1
    @JörgWMittag See above. I feel that answering: "no, you cannot write a program to calculate the Big-O of functions" is not an accurate answer for what OP was asking. It may be true that you can't calculate the Big-O of all functions but, I am in agreement with Flater that, OP's question, as it is worded, doesn't imply "all functions" as a requirement. Commented Feb 3, 2020 at 20:46
-1

Very short answer: this is impossible, since it can be used to solve the Halting Problem.

Intuitive answer #1: "What is the algorithmic complexity of this code" is clearly a more complicated question than "Does this code stop", which we know is undecidable. If such a simple question is undecidable, then a more complicated question probably is, too.

Intuitive answer #2: If it were possible to write such a tool, then I could simply check whether the return value is smaller than infinity and solve the Halting Problem this way. Since we know the Halting Problem is undecidable, such a tool cannot possibly exist.

Correct answer: (The correct answer would be a proof of the undecidability, which I will not give here. There is a sketch of a proof in this answer to a very similar question on our sister site Stack Overflow.)

Improve this answer
4
  • 3
    You're succumbing to a logical fallacy. "Not always" does not equate to "never". The Halting Problem: "Turing proved no algorithm exists that always correctly decides whether, for a given arbitrary program and input, the program halts when run with that input." It does not state that you can never do it, it states that you can't always do it. A more explicit quote: "While deciding whether these programs halt is simple, more complex programs prove problematic." Some (sufficiently simple) programs can be defined as halting or not. Commented Jan 31, 2020 at 10:31
  • 2
    @Flater You could write something that categorises things into Some O() | Doesn't Halt | Don't Know, but most of the interesting programs live in Don't Know Commented Jan 31, 2020 at 10:50
  • 2
    @Caleth: Indeed. People often both underestimate and overestimate the importance and reach of the HP. Microsoft Research's Terminator (which now ships as part of the Windows Driver Development Kit) does check whether code halts. BUT! This only works for a very restricted subset of programs, namely Windows device drivers written in a specific restricted subset of C++ in a specific style against a specific restricted set of APIs and even then, there are many cases where it can neither prove termination nor non-termination, and thus has no choice but to reject the driver. Commented Jan 31, 2020 at 12:03
  • 2
    @Caleth: Even if it can only answer trivial functions, it would still have a purpose as either a training tool or a safety guard against (or to point out) simple mistakes. Not every bug is intricate, not every test is testing contrived behaviors. Commented Jan 31, 2020 at 12:49

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.