Big O notation

[simorgh]

May some one explain about Big O notation?

Is there any software to analyze it when you are working with JAVA code?Or any JAVA IDE does that?

[Fubarable]

May some one explain about Big O notation?

Rather than ask someone to repeat a chapter and verse that's already been written, you are probable much better off reading the Wikipedia article (or the many articles found on Google), and then ask specific questions on what it is you don't understand in the articles. That way you'll save folks from typing out pages of info that you already know, and that way we have a much greater chance of being able to help you.

Is there any software to analyze it when you are working with JAVA code?Or any JAVA IDE does that?

Not that I know of, but Google again knows much more than me in this regard.

Edit: although I'm not sure how software can do this -- analyze algorithms of code written in Java -- or if it's even possible.

Much luck!

[JosAH]

Edit: although I'm not sure how software can do this -- analyze algorithms of code written in Java -- or if it's even possible.

It can't be done; embed two differnt big-Oh algoritms in a decision that involves an undecidable problem:

if (PostCorrespondenceProblem(pcp)) // is pcp solvable?
   // do something, say, O(n^2)
else
   // do something else, say, O(2^n)

To be able to answer this big-Oh question the analyzer has to be able to solve any instance of a pcp and it can't do that.

kind regards,

Jos

[Fubarable]

It can't be done; ....

Thanks for elucidating this!

[JosAH]

Thanks for elucidating this!

No problem, you're welcome; those undecidable problems are my favourites; they save (lazy) math folks a lot of tedious proving: simply reduce another problem to one of those and you're ready, no more discussion about it ;-)

kind regards,

Jos

[developersh]

May some one explain about Big O notation?

Is there any software to analyze it when you are working with JAVA code?Or any JAVA IDE does that?

Actually Big o notation shows that complexity of your code in a program & the it will be upper limit of your complexity means that how much time will be exceed to execute the code Big O notation describe as O(n) < O(log n) < O(n*n)<O(n*n*n) like wise

[JosAH]

Actually Big o notation shows that complexity of your code in a program & the it will be upper limit of your complexity means that how much time will be exceed to execute the code Big O notation describe as O(n) < O(log n) < O(n*n)<O(n*n*n) like wise

O(n) < O(log n)? I don't think that can be true.

kind regards,

Jos

[iluxa]

Big-O notation means this:

f(n) = O(g(n)) iff exist integers N, C such that for all x > N, f(x) < C*g(x)

N means "the condition will work for all large integers after N". For example, consider these functions:
f(x)=10*x
g(x)=x^2

which one is larger?

makes sense that g(x) is larger, but if you take x=5, it doesn't hold. N in the formula above means you can ignore all small x, so you can say this: g(x)>f(x) for all x>100, and thus, f(x) is O(g(x)).

now consider these two functions:

f(x)=x^2+10
g(x)=x^2

makes sense they should be equally large: when x grows, the +10 will not really matter. for that, in definition above they introduce constant C. So you can say this: for all x>100, since f(x)<2*g(x), and thus, f(x) is O(g(x)).

In practice:

if you have a polynom, it's O(x^highest power). so 3*x^2+21x+48 is O(x^2)

x < log x < sqrt x < x < x logx < x^2 < x^2 log x < x^3 ... < 2^x

2^x = e^x = 3^x = anything^x < x^x

n! is its own thing...


hope that helps

[JosAH]

n! is its own thing...

No it isn't, you can use Stirling's approximation.

kind regards,

Jos

[iluxa]

sh-h-h! I'm trying to keep things relatively simple here!

[JosAH]

sh-h-h! I'm trying to keep things relatively simple here!

Sorry 'squire, it won't happen again, promised.

kind regards,

Jos

ps. n! < n^n

[iluxa]

can you prove that an array cannot be sorted in better than n log(n)?

[JosAH]

can you prove that an array cannot be sorted in better than n log(n)?

There's a nice proof in Donald Knuth's "The Art Of Computer Programming" vol III: "Searching and Sorting". I also found another (similar) proof here.

kind regards,

Jos

[simorgh]

O(N) = as you increase the size of input, the time taken to complete operations scales linearly with that size

Big O specifically describes the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm.

When I check images in this site:

An Intro to Big Oh Notation with Java « NerdGerl

I see they use big O in order to find the relationship between size on input and time.In fact, I think Big o is a function that represent If size of input being increased, How much time of running of algorithm will be increase. Is it right?

But then there is another question, If it is about the size of input, Then size of for example a number, will be unlimited. then there is worst case after worst case.Then we can not say this is the worst case, because there is another worst case too.



I really get confused!


Another question:

k=0;
for(i=0; i<n; i++)
k++

It is said the worst case here is : o(n)

Now my question is:

If it is the worst case, Then what can be the average case for this?
&gt;

[JosAH]

Another question:

k=0;
for(i=0; i<n; i++)
k++

It is said the worst case here is : o(n)

Now my question is:

If it is the worst case, Then what can be the average case for this?
&gt;

That example doesn't show what your problem is about: its worst case is also its best case and its also its average case. Take this example: let int[] array be an unsorted array of length n. Searching for a number m takes n steps worst case, n/2 steps average case and 1 step in the best case. The worst case and average case are both O(n). The best case takes O(1) steps in the rare event that the first array element is the wanted element.

kind regards,

Jos

[simorgh]

k=0;
for(i=0; i&lt;n; i++)
k++;
k=0;
for(j=0; j&gt;&lt;n; j++)
k++;
Sequential for loops are not related and loop independently of each other. The first loop will execute
n times. The second loop will execute n times after the first loop finished executing. The worst case
timing will be:
O(n) + O(n) = 2 * O(n) = O(n)
We drop the constant because constants represent 1 time unit. The worst case timing is O(n).

I read this in a tutorial.

May you explain more about this:

O(n) + O(n) = 2 * O(n) = O(n)

Another question:

k=0;
for(i=0;i<n;i++)
for(j=i;j<n;j++)
k++;

In this situation we calculate the worst case timing using both loops. For every i loop and for start of
the inner loop j will be n-1 , n-2, n-3…
O(1) + O(2) + O(3) + O(4) + ......
which is the binomial series:
n ( n - 1) n^2 - n n^2
------------ = ----------- = ------ = O(n2)
2 2 2

May you explain more about this


third question

k = 0;
for(i=1; i<=n; i=i*2)
for(j=1; j<=i; j++)
k++;

What is Big O for this code?

[JosAH]

May you explain more about this: [ ... ]
Another question: [ ... ]
May you explain more about this [ ... ]
third question [ ... ]

Do you want fries on top of that?

kind regards,

Jos

ps. do your own homework.

[simorgh]

It is not the home work, Just a few questions

[JosAH]

It is not the home work, Just a few questions

Well, then show some effort; we are not a free answering service here.

kind regards,

Jos