willisoften Posted January 1, 2004 Report Share Posted January 1, 2004 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? Quote Link to comment Share on other sites More sharing options...
dino_bosnia Posted January 1, 2004 Report Share Posted January 1, 2004 (edited) <!--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 Quote Link to comment Share on other sites More sharing options...
fuzzylizard Posted January 1, 2004 Report Share Posted January 1, 2004 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. Quote Link to comment Share on other sites More sharing options...
willisoften Posted January 3, 2004 Author Report Share Posted January 3, 2004 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! Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.