algorithm - Programmatically obtaining Big-O efficiency of code

Question

I wonder whether there is any automatic way of determining (at least roughly) the Big-O time complexity of a given function?

If I graphed an O(n) function vs. an O(n lg n) function I think I would be able to visually ascertain which is which; I'm thinking there must be some heuristic solution which enables this to be done automatically.

Any ideas?

Edit: I am happy to find a semi-automated solution, just wondering whether there is some way of avoiding doing a fully manual analysis.

question from:https://stackoverflow.com/questions/480775/programmatically-obtaining-big-o-efficiency-of-code

Answer 1

It sounds like what you are asking for is an extention of the Halting Problem. I do not believe that such a thing is possible, even in theory.

Just answering the question "Will this line of code ever run?" would be very difficult if not impossible to do in the general case.

Edited to add: Although the general case is intractable, see here for a partial solution: http://research.microsoft.com/apps/pubs/default.aspx?id=104919

Also, some have stated that doing the analysis by hand is the only option, but I don't believe that is really the correct way of looking at it. An intractable problem is still intractable even when a human being is added to the system/machine. Upon further reflection, I suppose that a 99% solution may be doable, and might even work as well as or better than a human.