Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

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

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

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

```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).```

```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])```

```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])```

```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])```

```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.  Reply With Quote

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

```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.  Reply With Quote

4. ## The Following User Says Thank You to helloworld922 For This Useful Post:

EDale (September 18th, 2013)

5. ## 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!  Reply With Quote

6. ## 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).  Reply With Quote

7. ## 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:

```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.  Reply With Quote 