2
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?

snapGeek
  • 41
  • 1
  • 2
  • 5
  • You should see this for more correct answer: https://stackoverflow.com/questions/48076176/time-complexity-and-integer-inputs/48076437#48076437 – libik Jan 03 '18 at 11:30

4 Answers4

5

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

Antonín Lejsek
  • 6,003
  • 2
  • 16
  • 18
  • This answer is only partially correct as mentioned at: https://stackoverflow.com/questions/48076176/time-complexity-and-integer-inputs/48076437#48076437 – libik Jan 03 '18 at 11:30
3

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.

Todd Resudek
  • 123
  • 5
0

Time Complexity of i*=2 or i/=2 will be the same and it will be log2(n).

AmAn KumAr
  • 376
  • 2
  • 12
-2

Misread i*=2 as i+=2.

It's just O(N), more precisely it would be O(N/2).

Why would you think that this would be O(log N)?

Justin Chou
  • 9
  • 3
  • Because for the following code its O(log N): for(int i=1;i – snapGeek Oct 16 '16 at 01:55
  • O(log(n)) - Logarithmic Examples: for(int i = 1; i <= n; i = i * 2) print "hello"; http://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly – snapGeek Oct 16 '16 at 01:56