4

Does anyone know of any program/script to calculate the computational complexity of code (e.g. method function) automatically?

If not, is there a good way (e.g. a design pattern, algorithm, etc) that supports it?

I'm not trying to do this in general.

In most cases, I know the input, the algorithm running it, and what constitutes a halt. I'm trying to compare 2 or more algorithms this way.

E.g.

algo #1 - 2x^2 + 10x + 5

algo #2 - 5x^2 + 1x + 3

Both algorithms are O(N^2). But algo #2 is better in the short run, while algo #1 is better in the long run.

kev
  • 1,085
  • 2
  • 10
  • 27
  • Do you mean 'is there a program which reads the source code for a function and writes an equation for the computational complexity of that function' ? That seems to be the thrust of your first sentence, but the rest of your question confuses me. Ah ha, I'm not the only one confused. – High Performance Mark Apr 04 '12 at 09:46
  • Also, are you looking for the theoretical computational complexity or the empirical computational complexity? – Franck Dernoncourt Apr 04 '12 at 10:04
  • 7
    http://en.wikipedia.org/wiki/Halting_problem – Irit Katriel Apr 04 '12 at 10:21
  • Thank you Katriel... when I read this question It sounded really familiar, but I didnt remembered where it was. – UmNyobe Apr 04 '12 at 12:23
  • 1
    possible duplicate of [A tool for calculating the big-O time complexity of Java code?](http://stackoverflow.com/questions/9958299/a-tool-for-calculating-the-big-o-time-complexity-of-java-code) – templatetypedef Apr 04 '12 at 18:47
  • This seems an interesting question – Faizan Mar 03 '13 at 21:00

2 Answers2

1

While it is impossible to develop an algorithm that solves your problem generally, you can write an algorithm that will calculate the complexity of a piece of software for a few example inputs.

The only software I can find reference to is called Trend-Profiler. But, if you are more interested in the algorithm than the result, there is a paper here that describes the software and its algorithm.

john_science
  • 6,325
  • 6
  • 43
  • 60
0

Wouldn't it be better to sample an algorithm with a different amount of inputs? With the time calculated for each input, you could approximate the complexity function and therefore determine whichever algorithm is better and at which stage.

Bartlomiej Lewandowski
  • 10,771
  • 14
  • 44
  • 75