# Big O notation

May some one explain about Big O notation?

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

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!

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.

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.

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