why it runs in O(n) it seems to be O(N * log N)

# Why it runs in O(n) it seems to be O(N * log N)

**singhpyro08**#2

inner loop runs for:

N, N/2,N/4…N/(infinite)

summing all:

N(1+1/2+1/4+1/8+…+1/inf)

all terms after will add upto 1 at max;

so this summation is N

so running time is O(N)

**chiragmidha**#4

It will be executed N + N/2 + N/4 + N/8 … times and if you will add all those you will approximately get 2N, which is of the order of N