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

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!

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.