Big O notation

Get Started
1

May some one explain about Big O notation?

Is there any software to analyze it when you are working with JAVA code?

2

I read this somewhere:

  1. linear for loops: O(n)
    k=0;
    for(i=0; i<n; i++)
    k++
    For loops are considered n time units because they will repeat a programming statement n times.
    The term linear means the for loop increments or decrements by 1

Does it mean it takes 3 sec? 3 milisecond??

Is it possible to estimate the maximum time that is needed for an algorithm by big O?For example say this code takes 20 sec!

3

http://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

The explanation at the link above seemed reasonable.

My guess is that some bench marking software should be able to tell you where you will run into Big O problems.

4

I saw something once(the name escapes me) that estimated the big o, but the way it worked was by just feeding increasingly larger datasets and using the differences in execution speed to estimate the complexity. That won’t always work well, mainly because big o is more intended to define the upper bound(worst case).

For example, quicksort has a quadratic complexity(pretty bad), but in the average case, not the worst case, its very efficient. This is why trying to estimate the big o by benchmarking is innacurate. The benchmark isn’t guaranteed to encounter the worst case, and it needs to.

5

My guess is that some bench marking software should be able to tell you where you will run into Big O problems.

Thanks friends for answer!

How to do that benchmark?Is there any JAVA IDE do that?

6

Still looking for a product that will do bench marking, but found the following link that was interesting:
http://www.ibm.com/developerworks/java/library/j-benchmark1.html

Here are some profilers that I found:
http://www.eclipse.org/articles/Article-TPTP-Profiling-Tool/tptpProfilingArticle.html
http://yourkit.com/overview/index.jsp
http://www.ej-technologies.com/products/jprofiler/overview.html
http://www.javaperformancetuning.com/tools/optimizeit/index.shtml

I’m not sure if the above products will be able to tell you about code complexity, but they should be able to tell you where most of your processing time is spent. Which isn’t quite what you’re asking for, but you should be able to figure out our calculations using the time spent in your algorithm methods.