Results 1 to 10 of 10
Thread: BigO Notation
 02222012, 08:46 PM #1Senior Member
 Join Date
 Oct 2011
 Posts
 115
 Rep Power
 0
BigO Notation
I have two problems that I think I know, but I'm not sure..
b.Java Code:int N; // N is given a value int loopVar = N; while (loopVar>0) { System.out.println( loopVar); loopVar = loopVar / 2; }
c.Java Code:int sum = 0; for (int i=0; i<n; i++) for (int j=0; j<i; j++) sum = sum + j;
 02222012, 08:54 PM #2
Re: BigO Notation
The first one seems reasonable, but I'm not convinced you're right about the second one. Why don't you write a small program that runs through this, counting the number of times the sum is incremented compared to n?
Hint What would happen if your first loop was reversed (went from n1 to 0 instead of 0 to n1)?How to Ask Questions the Smart Way
Static Void Games  GameDev tutorials, free Java and JavaScript hosting!
Static Void Games forum  Come say hello!
 02222012, 09:13 PM #3Senior Member
 Join Date
 Oct 2011
 Posts
 115
 Rep Power
 0
Re: BigO Notation
I ran it with a different counter in each loop. The first loop only counted 10 times, but the second (inner for loop) went 45 times. Total being 55...which without the inner for loop would be 10 = O(N), but seeing how this one has the inner loop I still think O(N(logN)) looks right..??
 02222012, 09:24 PM #4
Re: BigO Notation
Well, I don't think you're right. Where are you getting the logN from?
How to Ask Questions the Smart Way
Static Void Games  GameDev tutorials, free Java and JavaScript hosting!
Static Void Games forum  Come say hello!
 02222012, 09:32 PM #5Senior Member
 Join Date
 Oct 2011
 Posts
 115
 Rep Power
 0
Re: BigO Notation
Not really sure..it just seemed like it was 10 times larger than logN (Any algorithm which cuts the problem in half)...how would you get a logN??
 02222012, 09:39 PM #6
Re: BigO Notation
I didn't get a logN. Where does the second "algorithm" (really it's an implementation of an algorithm, but that might be a bit pedantic) cut the problem in half?
Like I said, write a program that runs this algorithm with different values for N, and compare how many times you do go through the loop. You can even graph the values out to visualize the bigO curve.
Or you could think about what the program is doing in general. What's it doing the first time through the outer loop? The inner loop? The second time? Draw it out on a piece of paper if it doesn't all fit in your head at once.How to Ask Questions the Smart Way
Static Void Games  GameDev tutorials, free Java and JavaScript hosting!
Static Void Games forum  Come say hello!
 02222012, 09:49 PM #7Senior Member
 Join Date
 Oct 2011
 Posts
 115
 Rep Power
 0
Re: BigO Notation
So the first time through the loop...
Java Code:N Outer Inner 1 1 0 2 2 1 3 3 3 4 4 6 5 5 10
 02222012, 09:54 PM #8
Re: BigO Notation
Using only small number for N isn't really in the spirit of algorithm analysis, and it doesn't give you much useful information. What happens when N is 10, 100, 1000, 100000? Graph it out to see a curve. Is that curve linear? Logarithmic? Quadratic? Something else?
Hint: remember summations from one of the annoying math classes that were a prereq for this class?How to Ask Questions the Smart Way
Static Void Games  GameDev tutorials, free Java and JavaScript hosting!
Static Void Games forum  Come say hello!
 02222012, 09:57 PM #9Senior Member
 Join Date
 Oct 2011
 Posts
 115
 Rep Power
 0
Re: BigO Notation
The problem is that when we get an exam we will only be given the code, and have to decide which algorithm it is. Are there telltell signs when it comes to what the code/loops look like?
 02232012, 03:17 AM #10
Re: BigO Notation
You have to look at the bigger picture. What is the general behavior of the algorithm? What does it do as N goes up? If you increase N by 1, how many more calculations are added? You can't always figure that out be looking at small values for N, unless you immediately recognize the pattern.
How to Ask Questions the Smart Way
Static Void Games  GameDev tutorials, free Java and JavaScript hosting!
Static Void Games forum  Come say hello!
Similar Threads

+= notation
By sehudson in forum New To JavaReplies: 2Last Post: 03112011, 05:51 AM 
Big O notation
By simorgh in forum Advanced JavaReplies: 18Last Post: 07102010, 03:26 PM 
Big O notation
By vendetta in forum New To JavaReplies: 6Last Post: 01082010, 08:47 PM 
Big O Notation
By dsym@comcast.net in forum New To JavaReplies: 1Last Post: 02212009, 07:02 PM 
Big Oh Notation and Heaps
By gibsonrocker800 in forum Advanced JavaReplies: 8Last Post: 01252008, 11:06 PM
Bookmarks