Time Complexity

[anjalirai36 (Anjali Kumari)]

for(i=n;i>0;i/=2)
{
for(j=0;j<i;j++)
constant time
}
Is above questions time complexity O(n(logn)^2) ?

[pratyush63 (Pratyush Kumar)]

@anjalirai36
When i=n, inner loop will run till n
When i=n/2, inner loop will run till n/2
When i=n/4, inner loop will run till n/4
…
…
When i=1, inner loop will run till 1

So time complexity T(n) can be written as

T(n) = O(n + n/2 + n/4 + … 1) = O(n)

Hope this helps