Help with Big-O notation

[skeet123]

I have an assignment dealing with algorithms and Big O notation. I am a little confusded about this notation stuff. Here are a few of the questions on the assignment:

What is the O-notation for the following code?

cin >> N;
for (int count = 1; count <= N; count++) {
  for(int count2 = 1; count2 <= N; count2++) {
     cout << count1 + count2;
  }
}

a.	O(1)		c.	O(log N)
	b	O(N)		d.	O(N2)

Since there are two loops I thought that you would do this:
N*N = N^2 which would mean that the answer would be d, but after researching some on this subject I found this talking about Big O notation.
If the outer loop is based on N, and the inner loop is based on the outer loop counter, then it is based on the same thing:
That would mean the answer would be b. This is what I am confused about. Could someone elaborate on this.

4.2 What is the O-notation for the following code?

cin >> N;
for (int count = 1; count <= N; count++) {
   for(int count2 = 1; count2 <= count; count2++) {
      cout << count1 + count2;
   }
}

a.	O(log N)		c.	O(N2)
	b.	O(N)		d.	O(N3)

Same thing with this problem. I think the answer is b or c. But I am not sure if someone can explain this a little better I would really appreciate it.
Thanks.

[Narue]

>That would mean the answer would be b.
No, the answer is d. There's no question about it since the inner loop you posted relies on N, not the value of the outer loop counter.

Now, if you're talking about counter2 being set to counter1 and using it as N, the answer would still be d because Big-O is an upper bound. For example:

for ( int i = 0; i < 10; i++ ) {
  for ( int j = i; j >= 0; j-- )
    ;
}

When i is 9 then j runs the full length of the outer loop, which is O(N). Since the outer loop is O(N), that gives you O(N^2). If you use O(N) as the upper bound, you've basically lied about your algorithm even though when i is 0, the inner loop isn't ten iterations. Even if it's for one iteration of the outer loop, the upper bound of the algorithm is O(N^2).

If you're really interested in being precise, you can work out a detailed analysis based on the increasing inner loop iterations. But that's not always worth it, and certainly not for this question.

>Same thing with this problem.
This is another form of the example I just gave.

[skeet123]

Thanks Narue you helped me a bunch.

[Rashakil Fol]

If you're really interested in being precise, you can work out a detailed analysis based on the increasing inner loop iterations. But that's not always worth it, and certainly not for this question.

To give an example of what Narue's talking about, it's not too hard to see that the total number of times you output the value count1+count2 will be N the first time through, N - 1 the second time, N - 2, the third time, and so on.

Then the total number of times you print a number will be N + (N - 1) + (N - 2) + ... + 3 + 2 + 1. This is known to equal (N^2 + N) / 2. Then your running time is O(N^2), since N^2 /2 becomes the dominating term when N gets really large.

Once you've done this (or seen it) once or twice, it becomes obvious, and going through motions like these are a waste of time, anytime you come across some pair of for loops with a similar structure.