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