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

#1

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

#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)

#3

Think about how many times the statement

count += 1;

is executed.

#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