O-notation

[jack223]

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++)
 }

a) O (log N)
b) O (N)
c) O (N^2)
d) O (N^3)

outer loop is O(N)
and the inner loop is also O(N) so you multiply these together..
i'll get N*N = N^2 so the answer is "c" O(N^2)

but what if

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

count1 = N
count2 = N

count1 + count2 = N + N??

so what is the answer in this case??...O(N) or O(N^2)???

a) O (log N)
b) O (N)
c) O (N^2)
d) O (N^3)

[WolfPack]

Intuitively my answer will be O(N^2). Will look for a way to prove it( if that is correct).
Edit.
Hey. I just had a look at your first piece of code. What is the difference?

The loops are the same. The only difference is that the first one does nothing and the other adds and outputs the two counters. I dont think that will affect the O notation. Both pieces should have the same O notation.

Intuitively my answer will be O(N^2). Will look for a way to prove it( if that is correct).

Don't be tricked into doing his homework 4 him. Tee he he, unless u feel the need to. :-)

[WolfPack]

Don't be tricked into doing his homework 4 him. Tee he he, unless u feel the need to. :-)

:cheesy: Not a chance. I just did it so that I could learn something.expecting that if I gave the wrong answer someone will correct me and give reasons.