SO.For those who didn’t get in first go. They can understand it like this:
First of all, look at the outer loop. You can see it iterates until i < 1 or i = 0. So, outer loop executes for values for i = N, N/2, N/4 … N/2^k (executing k number of times)
N/2^k < 1
so, outer loop executes logN times.
Now, looking at inner loop. First of all, it executes for N times, then N/2 times then N/4 times until it reaches 1. Basically, executing logN times.
So, time complexity will be N + N/2 + … logN terms.
By Geometric progression:
a=N, r= 1/2, n= logn (Remember logn has base 2)
Also, using a^logb = b^loga and log2 is 1.
N((1- (1/2)^logN)/(1-1/2)) = 2N(1-(1^logN)/(N^log2)) = 2N(1-1/N)=2(N-1) = 2*N = O(N)
So, time complexity is O(N)