views:

220

answers:

1

I am looking for an algorithm analysis tool for java that can calculate Big 0 of a function. Ideal I would like to make it part of my build process, along side of my other code metrics tool. Even after searching on google I am unable to find any opensource of commercial tool. Any suggestion would be welcome

Thanks

+7  A: 

This isn't something that is generally doable automatically. Big-O analysis isn't a trivial thing.

Are you sure you're not looking for a profiler instead?


Big-O analysis of algorithms is usually done in the design phase, on pencil and paper. It's possible that some people write simple programs and use automated tools to measure and compare a prototype implementation of various algorithms to help the analysis, but even in that highly hypothetical case, Java would NOT be the language of choice (Haskell, maybe).

For applications written in a practical (but theoretically ugly!) language like Java, usually you design and analyze the algorithm prior to implementation, and then once you translate it in Java, you profile and optimize as/if necessary. At this point you should already know the Big-O complexity of your algorithm.

It may be a surprise to you, but suppose you have an implementation of some algorithm, and then you optimize it so that it's now twice as fast. Maybe three times. Maybe ten times faster. Maybe a million times faster!!!

And yet, in terms of Big-O analysis, its complexity remains the same! If you had a linear algorithm, the improved million-times-faster optimized version is still linear! If it was quadratic, it will remain so!

This is because a constant factor is insignificant for asymptotic analysis (i.e. how fast does it grow as the input size goes toward infinity?). A million is a big number, but it's still just a constant.

Another complicating factor is that asymptotic analysis actually have a threshold after which the bounds hold. That is, for smaller inputs, these bounds can be broken, but starting from this threshold towards infinity, the bounds must be respected. This makes automatic analysis by measurement very hard, since you don't know if you've reached the threshold or not.

I recommend reading some elementary computer science textbooks to learn more of the subject.

Fun fact: it's impossible to tell if a program will ever stop. This is known as the halting problem. It may seems ridiculous at first, but this has many serious theoretical consequences.

See also

Questions on Java profilers

polygenelubricants