int count = 0;
for (int i = N; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count++;
according to me first loop is running n+n/2+n/4+n/8… so
order is o(logn)
and the inner loop also n+n/2+n/4…o(logn);
so overall complexity is o(logn*logn);
please explain
How the time omplexity of this is o(n)
the inner loop is n times
first it will run for entirety of n times
next time for n/2 and so on
n + n/2 + n/4 so on
this is a gp with common ratio 1/2
sum of gp = a(1-r^n)/(1-r)
n(1-(1/2)^n)/(-1/2) ~~ 2n ~~ O(N)