PDA

View Full Version : O Notation question



WhiteShadow
02-06-2011, 07:24 AM
algorithm sum(int[][] a)
total = 0
for i = 0 to a.length do
for j = 0 to a[i].length do
total += a[i][j]
end for
end for
return total

Why is this O(n)? Shouldn't it be O(n^2)


Algorithm sneaky(int n)
total = 0
for i = 0 to n do
for j = 0 to n do
total += i * j

return total
end for
end for

And why is this O(1)? Why isn't this O(n^2) also?

Thanks,
WhiteShadow

HyperSecret
02-06-2011, 09:00 AM
AFAIK, they should be N^2. I didn't really like Big O Notation, i may be wrong. >.<

lordsaturn
02-06-2011, 09:12 AM
The second one is O(1) because as soon as it calls total += i*j for the first time, it exits the function with return total.

The first one i think is O(n) because n = a[0].length + a[1].length + a[2].length ... etc.

Wizzup?
02-06-2011, 10:07 AM
As far as I can see, the second one is O(n^2)
The first one is a bit more tricky, because the inner arrays can be less long, or longer. I think it's O(n^2) though, but it's been a long time since I worked with Big-Oh. :)

It really can't be O(1) or O(n) since O() describes the worst case / limiting behaviour.

WhiteShadow
02-06-2011, 06:01 PM
Thanks guys.

I guess the teacher may have written the wrong answers then (or I copied it wrong. >.>). lol

@ lordsaturn

Doesn't return only get called (second algorithm) after the two nested loops are finished? Which is n*n? I don't see what you're saying. "{

Method
02-06-2011, 06:09 PM
The second one does look like it is O(1). I think the reason you don't see it is because the indentation is funky. Notice how the code in the inner for loop does total += i * j (which takes some constant amount of time) and then returns. Since there are two "end for" statements after the return statement, you can see that the function will return after the first iteration of the inner loop.

Wizzup?
02-06-2011, 07:05 PM
The second one does look like it is O(1). I think the reason you don't see it is because the indentation is funky. Notice how the code in the inner for loop does total += i * j (which takes some constant amount of time) and then returns. Since there are two "end for" statements after the return statement, you can see that the function will return after the first iteration of the inner loop.

Oh, yeah... How's that for being a stupid assignment.

WhiteShadow
02-06-2011, 07:07 PM
The second one does look like it is O(1). I think the reason you don't see it is because the indentation is funky. Notice how the code in the inner for loop does total += i * j (which takes some constant amount of time) and then returns. Since there are two "end for" statements after the return statement, you can see that the function will return after the first iteration of the inner loop.

Ohhh I see what you mean. freakin' shitty pseudocode...

Now it makes sense!