How is the time complexity of the following while loop will be O(logn)?
Let N=16, number of iteration is
i | loop
--------
16 | 1
8 | 2
4 | 3
2 | 4
1 | 5
You can see log2(16) = 4 and the number of iterations is log2(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 = 2K Then K = log2(N)