Are there any tools that can determine perform code analysis for Big-O complexity?

Question

I haven't seen anything out there, and I suspect the difficulty with defining "n" since for generally for analyzing a complex function there'd be more than just one or two variables for defining.

There are analysis tools for cyclomatic complexity but are there ones for time (and/or space) complexity? If so which ones, if not, why not? Is it infeasible? Impossible? Someone just hasn't gotten around to it?

Ideally there'd be something like overall complexity for the application (defining different possible "n"s) as well as for each method in the app

Edit: So it seems like an exact solution is impossible because of the Halting Problem however, is some kind of heuristic approximation possible? I realize that for practical purposes a good profiler will give much more useful information, but it seems like an interesting problem.

Also, how about one that calculates for a certain subset of programs?

Answer 1

Unfortunately there is this problem called the Halting problem...

Answer 2

No, this isn't possible, due to the halting problem.

If you'd like to do this to improve your applications, you might consider profiling instead. It would allow you to pin-point what is actually taking the most time. This way you don't spend time optimizing a O(n^3) algorithm that only runs on small datasets.

Answer 3

Never seen a tool to do this but we utilize profiling tools to get a better idea where the bottlenecks are. It isn't always obvious and I've been surprised a few times by things that I thought took a long time actually taking very little and vice-versa. In the .NET world, I've used ANTS and the JetBrains tools.

Answer 4

A few thoughs:

Real computers are approximately deterministic finite state machines, so the halting problem isn't actually a practical limitation. A practical limitation is an algorithm that takes more time to run than you feel like waiting, ruling out any brute force methods of analysis.

To get a rough idea of complexity of an algorithm, you can always run it on a set of random inputs and measure the time taken. Then plot a curve through the data.

Analyzing the time complexity of algorithms can be fairly complicated, requiring some creative steps. (See for example analysis of quicksort). The problem is related closely to logical theorem proving and program verification. It might be feasible to construct a useful tool that enables semi-automatic solution of complexity, i.e. a tool that searches systematically for solutions given hints from a human, but it certainly isn't easy.