1. Member
Join Date
Jan 2010
Posts
25
Rep Power
0

## 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?Or any JAVA IDE does that?

2. Originally Posted by simorgh
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!
Last edited by Fubarable; 05-01-2010 at 01:38 PM.

3. Originally Posted by Fubarable
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:

Java Code:
```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

4. Originally Posted by JosAH
It can't be done; ....
Thanks for elucidating this!

5. Originally Posted by Fubarable
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

6. Member
Join Date
May 2010
Posts
1
Rep Power
0
Originally Posted by 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?
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

7. Originally Posted by developersh
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

8. Senior Member
Join Date
Mar 2010
Posts
266
Rep Power
8
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

9. Originally Posted by iluxa
n! is its own thing...
No it isn't, you can use Stirling's approximation.

kind regards,

Jos

10. Senior Member
Join Date
Mar 2010
Posts
266
Rep Power
8
sh-h-h! I'm trying to keep things relatively simple here!

11. Originally Posted by iluxa
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

12. Senior Member
Join Date
Mar 2010
Posts
266
Rep Power
8
can you prove that an array cannot be sorted in better than n log(n)?

13. Originally Posted by iluxa
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

14. Member
Join Date
Jan 2010
Posts
25
Rep Power
0
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:

Java Code:
```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;

15. Originally Posted by simorgh
Another question:

Java Code:
```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

16. Member
Join Date
Jan 2010
Posts
25
Rep Power
0
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.

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

Another question:

Java Code:
```k=0;
for(i=0;i&lt;n;i++)
for(j=i;j&lt;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

third question

Java Code:
```k = 0;
for(i=1; i&lt;=n; i=i*2)
for(j=1; j&lt;=i; j++)
k++;```
What is Big O for this code?

17. Originally Posted by simorgh
Another question: [ ... ]
third question [ ... ]
Do you want fries on top of that?

kind regards,

Jos

18. Member
Join Date
Jan 2010
Posts
25
Rep Power
0
It is not the home work, Just a few questions

19. Originally Posted by simorgh
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

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•