3

So I know from memory that a for loop that looks like: 

for( int i = 0; i > N; i++)

Will have an O(N) and for every inner loop added you just multiply it by N -- assuming it's the same for loop with just a different initial. My question is, for a loop like 

for( int i = 0; i < N; i *= 2) 
   for( int j = 0; j < N; j++)

I know from memory that the first loop would be lnN and the second would be N so O(NlnN) is the answer. But I don't want to memorize these big O's, I want to know how to actually compute them by hand, iow how to trace it with a given N. Could someone please show me some process on how to do this? I've looked at slideshows from college lectures, but they usually do basic loops. Thanks for the help and guidance!

I can trace it and find the iterations, but when it comes to actually getting Big O is where I crash

Chri
  • 31
  • 2
  • 1
    http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it – assylias Nov 06 '14 at 04:46
  • 1
    You have several typos in your examples, don't you? In the first you have `i > N` instead of `i < N`. Also in the second example in second loop you should have `j < N` if it is O(N ln N) as you said. – justanothercoder Nov 06 '14 at 04:48
  • I apologize for the unneeded question. I've been looking for something similar to mine, but kept getting something else. But what happens with a for loop that results with a harmonic series. – Chri Nov 06 '14 at 04:57
  • I looked at the question similar to mine, but it does much simpler problems. While the textbook the professor talked about does have harder problems, they're harder in terms of length not computing. – Chri Nov 06 '14 at 06:40

0 Answers0