1

I'm trying to understand why it's impossible to create a tool that calculates Big-O notation automatically.

I have read about Halting problems, but not related on Big-O notation and I was wondering, or at least have an example in which we're not able to determine a Big-O notation for a given function.

Can anybody give me such an example?

  • 1
    What is the big O for a function that never halts? – jk. Aug 1 '16 at 9:18
  • Would tell inifnite or N ? Or.. – mfrachet Aug 1 '16 at 9:19
  • 1
    if it said O(N) for not halting then you can never know if its output is correct is the algo linear or doesn't halt? If it says infinity then you have RemcoGerlish 's answer – jk. Aug 1 '16 at 9:40
  • 1
    You can obviously create a tool that calculates the runtime for some algorithms. (And fails for others). – gnasher729 Aug 1 '16 at 15:43
7

If you had such a tool, you could run it on any algorithm to figure out what it's Big-O was. If it returns a value less than infinite, then apparently the algorithm halts within time proportional to that. So you would have solved the halting problem, but we know that that is impossible. So you can't have such a tool.

  • This is of-course theoretically correct, but can't we calculate an estimate by setting limits? If we can calculate the result of 1, 10, 100 ... 10000, 100000 inputs, which is perfectly possible with small-enough tasks, we should have enough data points for an accurate estimate, right? – Mast Aug 30 at 9:58
  • 1
    @Mast: only in some cases, but then you have a normal profiler. IF you know the program always halts, IF you know a way to generate inputs for it that are representative for that input length, IF your general tool can generate inputs that fit that criterium for all algorithms given it and IF you can wait that long, then yes you can estimate. But generally you'd always build something like that on purpose for what you're trying to profile. – RemcoGerlich Aug 30 at 10:17
  • Right, so, it's possible but only in very limited circumstances. – Mast Aug 30 at 10:39
  • @Mast: yes, and the tool can't tell whether a given program fits in those limited cirumstances. – RemcoGerlich Aug 30 at 11:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.