Results 1 to 19 of 19
Thread: Big O notation
 05012010, 12:02 PM #1Member
 Join Date
 Jan 2010
 Posts
 25
 Rep Power
 0

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?
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; 05012010 at 12:38 PM.
 05012010, 12:44 PM #3
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,389
 Blog Entries
 7
 Rep Power
 25
It can't be done; embed two differnt bigOh 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)
kind regards,
Jos

 05012010, 01:05 PM #5
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,389
 Blog Entries
 7
 Rep Power
 25
 05022010, 05:48 AM #6Member
 Join Date
 May 2010
 Posts
 1
 Rep Power
 0
 05022010, 07:57 AM #7
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,389
 Blog Entries
 7
 Rep Power
 25
 05032010, 08:38 PM #8Senior Member
 Join Date
 Mar 2010
 Posts
 266
 Rep Power
 7
BigO 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
 05042010, 04:51 PM #9
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,389
 Blog Entries
 7
 Rep Power
 25
No it isn't, you can use Stirling's approximation.
kind regards,
Jos
 05042010, 07:14 PM #10Senior Member
 Join Date
 Mar 2010
 Posts
 266
 Rep Power
 7
shhh! I'm trying to keep things relatively simple here!
 05042010, 08:10 PM #11
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,389
 Blog Entries
 7
 Rep Power
 25
 05042010, 08:48 PM #12Senior Member
 Join Date
 Mar 2010
 Posts
 266
 Rep Power
 7
can you prove that an array cannot be sorted in better than n log(n)?
 05052010, 07:43 AM #13
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,389
 Blog Entries
 7
 Rep Power
 25
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
 07082010, 03:59 PM #14Member
 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 sizeBig O specifically describes the worstcase 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:
Java 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?
>
 07082010, 04:15 PM #15
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,389
 Blog Entries
 7
 Rep Power
 25
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
 07102010, 12:41 PM #16Member
 Join Date
 Jan 2010
 Posts
 25
 Rep Power
 0
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:
Java Code: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 n1 , n2, n3…
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
Java Code:k = 0; for(i=1; i<=n; i=i*2) for(j=1; j<=i; j++) k++;
 07102010, 01:05 PM #17
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,389
 Blog Entries
 7
 Rep Power
 25
 07102010, 03:21 PM #18Member
 Join Date
 Jan 2010
 Posts
 25
 Rep Power
 0
It is not the home work, Just a few questions
 07102010, 03:26 PM #19
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,389
 Blog Entries
 7
 Rep Power
 25
Similar Threads

Big O notation
By vendetta in forum New To JavaReplies: 6Last Post: 01082010, 08:47 PM 
Big O notation question
By kira137 in forum New To JavaReplies: 4Last Post: 10142009, 08:07 PM 
Big O Notation
By dsym@comcast.net in forum New To JavaReplies: 1Last Post: 02212009, 07:02 PM 
PostfixNotation
By little_polarbear in forum New To JavaReplies: 9Last Post: 09092008, 04:24 PM 
Big Oh Notation and Heaps
By gibsonrocker800 in forum Advanced JavaReplies: 8Last Post: 01252008, 11:06 PM
Bookmarks