Perl Monk, Perl Meditation PerlMonks

### Algorithm complexity

by fauria (Deacon)
 on Jul 07, 2009 at 22:12 UTC Need Help??
fauria has asked for the wisdom of the Perl Monks concerning the following question:

Dear Monks,

Does anyone know if there exists any tool that can automatically analyze the complexity of a given Perl algorithm, expressed in big O notation?

Thank you!

Replies are listed 'Best First'.
Re: Algorithm complexity
by jettero (Monsignor) on Jul 07, 2009 at 22:18 UTC

Usually the tool you'd use for that is a human being. I'd be pretty shocked if there were tools like that for any language that actually worked accurately. Although, I'm pretty sure I could detect for(){for(){}} and produce O(N^2).

It's not an exact science in any case. A lot of the cooler parts of the proofs tend to be knowing which parts of the math don't matter (and showing it). That's more like art. Mathematical art, but art. I dare a computer program to do it.

You might be able to get something to measure time slices for given inputs or something, ... I'm not sure that would really show big oh though.

-Paul

Re: Algorithm complexity
by moritz (Cardinal) on Jul 07, 2009 at 22:31 UTC
No. In general that problem is Turing-complete.

Heck, you can't even (in general) determine if a program will even terminate - how can you estimate the time until termination if you don't know if it will even terminate?

(Update: IMHO this is a nice example why it's good to have at least some scientific backing when you think about solving problems. Knowledge that it can't be solved in general prevents you either from wasting time, or helps you focusing on cases where it's feasible).

But you can tell that a program didn't finish after a given threshold (a week or so) without violating Turing's laws.

In theory it should be possible to approximate O(n) by benchmarking for increasing n and using numerical methods to interpolate the gotten data.

In praxis a human should define what exactly "n" is, the accuracy of the interpolation ( O(1) and O(log log n) can look very similar ;) and when to stop testing... with "enough" time for testing you'll certainly get a result...

Cheers Rolf

But you can tell that a program didn't finish after a given threshold (a week or so) without violating Turing's laws.

Yes, that's an incomplete solution. Which doesn't tell you anything about the asymptotic runtime if it didn't finish.

In theory it should be possible to approximate O(n) by benchmarking for increasing n and using numerical methods to interpolate the gotten data.

If you don't try it for all possible inputs you can miss worst case scenarios.

For example old versions of perl used to have an O(n) complexity for hash accesses if the keys followed a certain pattern that lead to 100% hash collisions - which was an attack vector for denial of service attacks.

(Newer perl versions solve that by randomizing hash seeds if too many collisions occur).

You not only have to specify what n in O(n) means, but also if you're talking about worst case, average case or amortized runtime.

Re: Algorithm complexity
by JavaFan (Canon) on Jul 07, 2009 at 23:42 UTC
Considering it's even impossible to write a program that determines whether another program terminates (Halting Problem), no such tool exists.

In general, not even humans can, or can only proof upper bounds which aren't tight (or not known whether the bounds are tight).

Re: Algorithm complexity
by Herkum (Parson) on Jul 07, 2009 at 22:32 UTC

As someone touched on the big O notation and I know nothing on that subject I will offer another tool for measuring complexity.

Look up on cpan McCabe which is a very simple formula for determining the complexity of a particular piece of code. You can also look up Cyclomatic complexity for a explanation of the subject.

Re: Algorithm complexity
by chomzee (Beadle) on Jul 07, 2009 at 22:31 UTC
I believe there is no such tool -- those are problems which computer scientists are supposed to solve. :)
Re: Algorithm complexity
by spx2 (Deacon) on Mar 12, 2010 at 12:23 UTC
I do not think what you want is possible(or at least I haven't read of anything that proves it is). However , you may try your luck with the following idea: The big O notation refers to classes of function growth, if you are able to measure the time it takes for your algorithm to finish for a reasonable number of values you can make a plot. If you are able to see which classes of functions that plot is most similar to then you are able to approximate where the big O notation will be. Again, this is in no way a rigorous solution, it might work on some problems though ... good luck.

Create A New User
Node Status?
node history
Node Type: perlquestion [id://778041]
Approved by jettero
help
Chatterbox?
Jar. Jar!...

How do I use this? | Other CB clients
Other Users?
As of 2018-03-24 20:37 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (299 votes). Check out past polls.

Notices?