O(N) is correct


#1

We have to see how many times count ++ executes…

IN a simple double for loop , where outer loop executes n times and inner executes m times, the complexity is O(nm) because for every run of outer loop, inner loop executes m times… Hence we can simply multiply there… The number of times count ++ will execute in a simple double loop is. m + m + m + … m (n times) . Hence complexity is O(nm)

In this case , the inner loop executes different number of times for each run of outer loop. We just need to add those number of times, same as above…

So, outer loop runs for logN times…
Complexity will be same as the total number of times count++ executes, which is equal to total number of times inner loop executes… which is…
n+ n/2^1 + n/2^2 + … n/2^logN

Taking N common…
= n (1+ 1/2 + 1/2^2 + …1/2^logN)

According to Geomeric Progression the sum of the series (1+ 1/2 + 1/2^2 + …1/2^logN)
(Refer https://www.mathsisfun.com/algebra/sequences-sums-geometric.html for formula of sum of this series)

a = N
n = logN
k= 1/2

= N ( 1-(1/2)^logN)/ (1 - 1/2)
= 2N (1 - 1/2^logN) < 2N

hence the answer is O(N)