Big-O Notation

[kraigballa]

I have two problems that I think I know, but I'm not sure..


b.

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.

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)

[KevinWorkman]

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)?

[kraigballa]

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..??

[KevinWorkman]

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

[kraigballa]

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??

[KevinWorkman]

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.

[kraigballa]

So the first time through the loop...

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)

[KevinWorkman]

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?

[kraigballa]

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?

[KevinWorkman]

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.