Software/script to calculate the computational complexity of code?

Question

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.

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
– High Performance Mark, Commented Apr 4, 2012 at 9:46
Also, are you looking for the theoretical computational complexity or the empirical computational complexity? — Franck Dernoncourt
– Franck Dernoncourt, Commented Apr 4, 2012 at 10:04
Thank you Katriel... when I read this question It sounded really familiar, but I didnt remembered where it was. — UmNyobe
– UmNyobe, Commented Apr 4, 2012 at 12:23
possible duplicate of A tool for calculating the big-O time complexity of Java code? — templatetypedef
– templatetypedef, Commented Apr 4, 2012 at 18:47

john_science · Accepted Answer · 2012-10-04 15:48:44Z

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.

answered Oct 4, 2012 at 15:48

john_science

6,5976 gold badges45 silver badges62 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Bartlomiej Lewandowski · Accepted Answer · 2012-10-04 16:27:41Z

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.

answered Oct 4, 2012 at 16:27

Bartlomiej Lewandowski

11.3k14 gold badges49 silver badges78 bronze badges

Collectives™ on Stack Overflow

Software/script to calculate the computational complexity of code?

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related