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

• September 18th, 2013, 05:16 PM
EDale
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.
• September 18th, 2013, 06:38 PM
helloworld922
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.
• September 18th, 2013, 06:49 PM
EDale
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!
• September 18th, 2013, 07:20 PM
helloworld922
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).
• October 1st, 2013, 01:31 AM
crazyjames
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.