The first time when i=N, inner loop goes for N. Second time, when i = N/2, the inner loop goes N/2 times. And so on. So, the body of inner loop is executed N + N/2 + N/4 + N/8 … = 2N times. Hence O(N).
// only see the solutions after trying hard & see this answer in solution section for more details
I see people having trouble with finding time complexity with nested loops like what to do multiply or add , lets see …
Every problem can be computed by addition method , they are actually same .
eg. for (i = n/2; i <= n; i++)
for (j = 2; j <= n; j = j * 2)
k = k + n/2;
In the above problem we see that the outer loop has complexity O(n)
and the inner loop has Olog(n), so the total time complexity is O(nlogn) which is correct
which can also be deduced in the following manner :
for each iteration of outer loop the inner loop gets executed fixed number of time (logn times)
so total time complexity is :
logn + logn +logn +…+logn = ‘n’ times logn = nlogn
(everything good till now)
now our problem
for (int i = N; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count += 1 ;
here we see outer loop is logn and inner loop is ‘n’ so time complexity is nlogn , which is WRONG.
because for each iteration of outer loop the number of times inner loops executes is not fixed but depends on that outer loop since here the condition in inner loop is (j=0; j<i; j++) but in last example it was (j=2 ; j<=n ; j=j*2) .
we see " j<i " so we know that number of times inner loop runs is not fixed (which in previous example was fixed) (try to dry run the code) so we cannot find time complexity by multiplying the outer and inner
loop’s complexity but we can find it by using a different application of multiplication i.e ADDITION
4*3 = 3+3+3+3
nlogn= logn+logn+logn…+logn (n times)
now : for each iteration of outer loop the inner loop gets executed some (not a fixed value) number of
see other comments for full maths derivation of GP and all.
remember we are not neglecting the outer loop in the same way in 4*3 = 3+3+3+3 we are not neglection the 4 but adding 3 four times.
If you still have doubts , read a basic programming book or watch some video , read the permutation and ‘counting number’ chapters in 11/12 maths book.