# Thread: Big-O Notation

1. Senior Member Join Date
Oct 2011
Posts
115
Rep Power
0

## Big-O 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;
}```
I would say O(log N)

c.
Java Code:
```int sum = 0;
for (int i=0; i<n; i++)
for (int j=0; j<i; j++)
sum = sum + j;```
I would say O(N(log N)) or maybe O(N^2)  Reply With Quote

2. ## Re: Big-O 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 n-1 to 0 instead of 0 to n-1)?  Reply With Quote

3. Senior Member Join Date
Oct 2011
Posts
115
Rep Power
0

## Re: Big-O 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..??  Reply With Quote

4. ## Re: Big-O Notation

Well, I don't think you're right. Where are you getting the logN from?  Reply With Quote

5. Senior Member Join Date
Oct 2011
Posts
115
Rep Power
0

## Re: Big-O 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??  Reply With Quote

6. ## Re: Big-O 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 big-O 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.  Reply With Quote

7. Senior Member Join Date
Oct 2011
Posts
115
Rep Power
0

## Re: Big-O 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```
You're right, the outer is never cut by half, but the inner does slowly increase as n increases. Not sure how to figure out which notation it is using. at this point it seems to be O(N+j) which would be O(N)  Reply With Quote

8. ## Re: Big-O 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?  Reply With Quote

9. Senior Member Join Date
Oct 2011
Posts
115
Rep Power
0

## Re: Big-O 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 tell-tell signs when it comes to what the code/loops look like?  Reply With Quote

10. ## Re: Big-O 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.  Reply With Quote

#### Posting Permissions

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