Big O revision

[willisoften]

I hate this stuff but have to revise it for an exam.

 

Unfortunately I have examples and no answers!

 

 

This is an example from a previous paper. Worth a staggering 1 mark.

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

 

O(2N) Any chance this is right?

[dino_bosnia]

<!--QuoteEBegin--><!--QuoteEBegin-->for(int i=0; i<n; i++)<!--QuoteEBegin-->   sum++;<!--QuoteEBegin-->for(int j=0; j<n; j++)<!--QuoteEBegin-->   sum++;<!--QuoteEBegin--><!--QuoteEBegin-->

 

O(2N)  Any chance this is right?

 

O(2N) ???

 

why did u use "for" loop???

Edited January 1, 2004 by dino_bosnia

[fuzzylizard]

The general rule when dealing with Big O notation is to drop the constant before the variable as the difference it makes is negligible. Therefore, it is just

 

O(n)

 

Not too bad for an algorithm.

 

As for whether that is correct or not, from the looks of it yes. The two loops are independent of one another, therefore, they do not really have any affect on one another. So yeah, you have O(2n) which is then simplified down to just O(n).

 

If the two loops where nested then you would have O(n^2) - O n-squared.

[willisoften]

I didn't use for loop! It's just an old exam question.

 

Thanks for your replies. I find it a big help to get answers as you can go back and look again.

 

Cheers!