Is Time complexity O(N) or O(Log N)?

Question

i = 1;
while(i<N) {
   i*=2;
}

I think the time complexity of the above code is O(N) but i'm not sure about it. Can you please let me know if you think its O(Log N) and the reason?

Solution 1

Time complexity si proportional to number of cycles. And number of cycles is exactly equal to Log(N)/Log(2), where Log is any logarithm. Or just Log2(N), where Log2 is logarithm with base 2. It is therefore O(Log N).

Solution 2

example: N = 10 while loop runs 1, 2, 4, 8, 16 (5 times)

if you double N, N = 20 you would expect the time complexity to also double if it were O(N). however, that loop runs 1, 2, 4, 8, 16, 32 (6 times)

and again, N = 40, that loop runs 1, 2, 4, 8, 16, 32, 64 (7 times)

This is O(log N) since the time complexity decreases as N becomes larger.

Comments

[snapGeek]

Because for the following code its O(log N): for(int i=1;i<n;i*=2)

[snapGeek]

O(log(n)) - Logarithmic Examples: for(int i = 1; i <= n; i = i * 2) print "hello"; stackoverflow.com/questions/2307283/…

[libik]

This answer is only partially correct as mentioned at: stackoverflow.com/questions/48076176/…

[Ajay Kr Choudhary]

Can you please add more explanation about why it is log2(n). It will help to improve the quality of the answer.