Big O notation... can you check my answers for each code segment?

Code java:

int sum = 0;
for (int i = 0; i < n; i += 2)
sum++; //I said this is O(log n) because if n=10 then this loop executes half the time. Not sure though. Or is it O(n)?

Code java:

int sum = 0;
for (int i = 0; i < n; i++)
sum++;
for (int j = 0; j < n; j++)
sum++; // I said O(n) for this one because it executes 2n times which is therefore O(n).

Code java:

int sum = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n[SUP]2[/SUP]; j++)
sum++; // my answer is O(n[SUP]3[/SUP])

Code java:

int sum = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < 2*i; j++)
sum++; //I think this is O(n[SUP]2[/SUP])

Code java:

int sum = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n2; j++)
for (int k = 0; k < j; j++)
sum++; //I think this is O(n[SUP]3[/SUP])

Code java:

int sum = 0;
for (int i = 1; i <= n; i = i[SUP]2[/SUP])
sum++; //and finally I think this one is O(log n)

Could you correct me? I want to see how well I know this.

Re: Big O notation... can you check my answers for each code segment?

1 is wrong. Hint: write out the expression for how many times the loop executes.

3 I'm assuming you meant the inner loop to be 0 to n*n (a.k.a. n squared)? If so, yes it is n cubed.

5 I think you have a typo in the actual code. Perhaps you meant this?

Code java:

int sum = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < n2; j++)
for (int k = 0; k < j; k++)

If so, you're not quite right because n2 does not have to equal n. Both terms should appear in the big O, though O(n^3) is not a bad approximation if n2 is approximately the same as n.

Re: Big O notation... can you check my answers for each code segment?

So for #1 if n=10 then the loop executes 5 times. So if it's not O(log n) then it must be O(n) because the number of times it executes is proportional to n? Is that right?

#3 yes that's what I meant, I guess the code didn't work! Thank you.

#5 so then it is O(n^2)? I'm a little lost, however thank you!

Re: Big O notation... can you check my answers for each code segment?

The reasoning for 1 is a bit convoluted. It is O(n) because you are running it half the time: O(n/2). But big-O drops the constant factors, so we're left with O(n)

#5 is not O(n^2). O(n^3) isn't a bad approximation, but it's a somewhat lazy answer. Read my hints about including n2 and n in the big-O (unless there were two typos in the original code).

Re: Big O notation... can you check my answers for each code segment?

O(log n) would basically be if each iteration you are dividing the remaining elements in half (i.e.- traversing a binary search tree). So an example of something that would look like O(log n) in a for loop could be:

Code :

for(int i = 1; i <= n; i = i * 2)
{
//some code
}

if n was 32, i would progress as follows: 1, 2, 4, 8, 16, 32. Notice if there were 32 elements, it only took until the 5th iteration to get to 32. log (base 2) 32 = 5 or 2^5 = 32. Hence it is O(log n). Now this could change depending on what was in place of //some code. For instance, inside the loop, if you looked through the entire set of n elements (or had the potential to look through them all, say in a linear search) then you could say O(n log n). This was a very basic explanation but hopefully it makes at least O(log n) a little easier to understand.