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?

Printable View

- 05-01-2010, 01:02 PMsimorghBig 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? - 05-01-2010, 01:20 PMFubarable
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.

Quote:

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

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! - 05-01-2010, 01:44 PMJosAH
It can't be done; embed two differnt big-Oh algoritms in a decision that involves an undecidable problem:

Code:`if (PostCorrespondenceProblem(pcp)) // is pcp solvable?`

// do something, say, O(n^2)

else

// do something else, say, O(2^n)

kind regards,

Jos - 05-01-2010, 01:51 PMFubarable
- 05-01-2010, 02:05 PMJosAH
- 05-02-2010, 06:48 AMdevelopersh
- 05-02-2010, 08:57 AMJosAH
- 05-03-2010, 09:38 PMiluxa
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 - 05-04-2010, 05:51 PMJosAH
No it isn't, you can use Stirling's approximation.

kind regards,

Jos - 05-04-2010, 08:14 PMiluxa
sh-h-h! I'm trying to keep things relatively simple here!

- 05-04-2010, 09:10 PMJosAH
- 05-04-2010, 09:48 PMiluxa
can you prove that an array cannot be sorted in better than n log(n)?

- 05-05-2010, 08:43 AMJosAH
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 - 07-08-2010, 04:59 PMsimorghQuote:

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

Quote:

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.

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:

Code:`k=0;`

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

k++

Now my question is:

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

> - 07-08-2010, 05:15 PMJosAH
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 - 07-10-2010, 01:41 PMsimorghQuote:

k=0;

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

k++;

k=0;

for(j=0; j><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)

May you explain more about this:

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

Another question:

Code:`k=0;`

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

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

k++;

Quote:

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

Code:`k = 0;`

for(i=1; i<=n; i=i*2)

for(j=1; j<=i; j++)

k++;

- 07-10-2010, 02:05 PMJosAH
- 07-10-2010, 04:21 PMsimorgh
It is not the home work, Just a few questions

- 07-10-2010, 04:26 PMJosAH