Big-O notation and halting problems

Question

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?

Answer 1

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.