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!
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.
 [reply] 
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. :)  [reply] 
Re: Algorithm complexity by moritz (Cardinal) on Jul 07, 2009 at 22:31 UTC 
No. In general that problem is Turingcomplete.
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).  [reply] 

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...
 [reply] 

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.
 [reply] 


 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.
 [reply] 
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).  [reply] 
Re: Algorithm complexity by spx2 (Chaplain) 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.  [reply] 

