for i = N and j = N times

for i = N/2 and j = N/2 times

for i = N/4 and j = N/4 times

total number of times = N + N/2 + N/4 + …+ N/(2^k)

= N ((1 - 1/(2^(k+1))/(1-1/2))

considering N/2^k <=1

~ 2^k = N

total number of times = 2N (1-1/2N)

= 2N(2N - 1)/2N

= O(N)