# Big-O notation and halting problems

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?

• What is the big O for a function that never halts?
– jk.
Aug 1, 2016 at 9:18
• Would tell inifnite or N ? Or.. Aug 1, 2016 at 9:19
• 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, 2016 at 9:40
• You can obviously create a tool that calculates the runtime for some algorithms. (And fails for others). Aug 1, 2016 at 15:43

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, 2019 at 9:58
• @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. Aug 30, 2019 at 10:17
• Right, so, it's possible but only in very limited circumstances.
– Mast
Aug 30, 2019 at 10:39
• @Mast: yes, and the tool can't tell whether a given program fits in those limited cirumstances. Aug 30, 2019 at 11:34