I did not understand how this piece of code will generate a complexity of O(log n).how many times the statements inside the loop will work?

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

CodePudding user response：

Let N=16, number of iteration is

i | loop
--------
16 | 1
8  | 2
4  | 3
2  | 4 
1  | 5

You can see log₂(16) = 4 and the number of iterations is log₂(16) 1. Or you can create a formulation for it f(N) = F(N/2) 1. Let suppose we have N = 2^K and so we have:

F(N) = F(N/2)   1 
F(N) = F(N/4)   1   1 
F(N) = F(N/8)   1   1   1 = F(N/(2^3))   3
...
...
...
F(N) = F(N/2^K)   K => F(2^K/2^K)   K => F(1)   K => 1   K

So if N = 2^K Then K = log₂(N)

CodePudding user response：

The number of iterations of the loop is the number of significant bits in N because i is halved at the end of each iteration. Hence the loop iterates log₂(N) times for N>0 and none otherwise. Each iteration has 3 simple operations, an addition, a division and a test, so the time complexity is O(log(N)).