What is the time complexity of following code:

Question

What is the time complexity of following code:

int a = 0, i = N; 
while (i > 0) { 
    a += i; 
    i /= 2; 
}

Answer 1

It's complexity will be O(logn). On every iteration, value of n will be divided by 2, i.e. n + n/2 + n/4 + n/8 ... 1.

To understand logn check this out