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

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.

Edited 4 Years Ago by histrungalot: n/a

This article has been dead for over six months. Start a new discussion instead.