Big(O) time complexity unable to find

Question

What is time complexity of following code :

int count = 0;
for (int i = N; i > 0; i /= 2) {
     for (int j = 0; j < i; j++) {
          count += 1;
     }
}

**

is it O(n) or O(log(n)*n)?

**

Answer 1

I think this type of question has already been answered in past posts. I'll cover the basic premise for this one. Suppose N = 8

First Loop (i)    No. Of Second Loop Runs 
8                 8
8/2               8/2
8/4               8/4
8/8               8/8

Generalizing & adding up no. of times second loop will run for above process:

N + (N / 2) + (N / 4) + ... + 1

We need to solve the above series to get overall time complexity. Let's take a case where this series is infinite (very large). In that case the formula for this kind of summation is

a + (a / r) + ... = a / (1 - r), where a is first term and r is common ratio

So, result will be:

N + (N / 2) + (N / 4) + ... = N / (1 - (1/2)) = (2 * N)

This is the maximum (upper-bound) of the series sum. 2 is a constant term . So we can conclude time complexity for worst case will be O(N).