Alright, I understand some of the basics of big O notation, but I have a test coming up in a few days and I need a bit of help. I understand that if you have a loop that iterates i*=2 then it would run lg(n+1) as log base 2 and +1 to exit the loop. And log base 3 if i*=3 and so forth. Then in loops inside of it you would continue to multiply n as well as still considering +1 to exit those loops and so forth. As things inside of the loops only execute n times. The problem am I trying to figure out is what happens if the loop iterates i%=2 or any number. And also I am stumped if it is i/=number. Would it still be logarithmic or would it not?

ex:

``````i = 1;          c1(1)
while (i <= m)  c2(lg(m+1))
i *= 2;         c3(lg(m))``````

so, O(lg(m))

but, this one confuses me,

``````for(i = 0;i < n; i++)    c1(n+1)
if(i % 2 == 0)           c2(n)
cout << i;               c3(???)``````

and what if that was i / 2 ?

This is probably really simple but I cannot wrap my head around it.

Here is another one but I am not sure if I am right or wrong on it,

``````for(i=0;i<n;i+=2)   c1(n+1)
cout << n;          c2(n)
O(n)``````

if it is just i++ I have no problem

## All 5 Replies

I am still trying to figure this out if anyone could help me I would appreciate it.

The cout in the if of i%2 would be c3(n/2) because every even number the statement will be true.
And the plus 2 looks right.
If I'm wrong don't worry 20+ people will be happy to point out I'm wrong. Either way you get an answer

As for the i/2, the question would be what is the if checking.
If it was `if (i/2 == 0)` then c3(2). One for 0/2 and one for 1/2. The number of time the cout executes is based on the if check.

so if it were

``````for(i=n;i>=1;i/=2)
cout << x;``````

so here I could say c1 is n+1 and c2 is n(2)?
I am a little confused because on a problem like,

for(i=1;i<=16;i*=2)
cout << i;
c1 would be lg(n+2) but why not lg(n+1)? where is the extra + 1 coming from. I realize there is a +1 for exiting the loop but if it because of going from 1 to exactly the value 16 then I understand where the extra +1 is coming from. But, there are problems that do the same thing that are still only +1 such as,

i=1;
while(i<=m)
i*=2;

here c2 would be lg(m+1). I have no idea what the difference is??? Please if someone could help me lol I am having a hard time...

``````for(i=n;i>=1;i/=2)
cout << x;
// And
for(i=1;i<=16;i*=2)  c1(6) -> log(16) + 2
cout << i;                c2(5) -> log(16) + 1
// are the same``````

An O(log(n)). As for the for loop and the +2, not sure.
The for loop executes 1, 2,4,8,16,32 -> 6 times and the cout 5 times.
So I'm still thinking about it. Thoughts.

Be a part of the DaniWeb community

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