CODEWITHSUNDEEP
algorithm
kev
kev

Reputation: 1115

Software/script to calculate the computational complexity of code?

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.

Upvotes: 4

Views: 1910

Answers (2)

Bartlomiej Lewandowski
Bartlomiej Lewandowski

Reputation: 11180

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.

Upvotes: 0

john_science
john_science

Reputation: 6541

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.

Upvotes: 1

Related Questions