Member Avatar for 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)

  • 3 Contributors
  • 3 Replies
  • 93 Views
  • 6 Hours Discussion Span
  • Latest Post Latest Post by WolfPack
Member Avatar for 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.

Member Avatar for iamthwee

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. :-)

Member Avatar for 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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.