For me it looks like N

programming
Tags: #<Tag:0x00007f1827e669c8>

#1

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)