How to find the Big-O complexity mentioned below

Question

Could you guys help in understanding the time complexity of the below code -

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

It was my underdstanding that this should be O(nlogn) but that is wrong. Just to update why I thought it would be O(nlogn) because in the first loop, we are dividing the i by 2 meaning we are cutting it in half, so that would be log n and in the inner loop we are running it till i, so it would be N, so complexity would be O(nlogn) Thanks in advance

Answer 1

The inner loop is easy - goes each time from 0 till j. so now we only need to understand what j is on each iteration.
The outer loop starts with N and cut in half each time, so it means that the first round will be N, the second N/2, the third N/4 and so on.

So we have N + N/2 + N/4 + N/8 .... which sums up to 2N operations. So the complexity is o(N)

Answer 2

As others have pointed out, each time the outer loop iterates, the inner loop performs half of the iterations, starting by N:

N + N/2 + N/4 + N/8 ...

That will go on until a division is 0. However, in terms of upper-bound complexity, it is typical to consider the case of the infinity, that means, imagining that the series goes on and on and on... but we can find a converging value.

In this particular case, we find that, extracting the common factor, we're left with:

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

The first thing is just N, and the second factor is a geometric series, which terms are of the form 1/2^n. (formula and further explanation here)

In short term, that second factor, the infinite sum, converges to 2. So in total we have 2N, which in terms of complexity is equivalent to N.

Answer 3

In this case, the complexity is O(2N) which is equivalent to O(N).

Why:

You have 2 loops, the outer one gets half of N each time (except the first round) and the inner one goes from 0 to that half of N, which indicates in the first inner loop it goes [0, N) then [0, N/2), [0, N/4), ...

Therefore total number of times is N + N/2 + N/4 + ... equals to N * (1 + 1/2 + 1/4 + 1/8 + ...) and since 1 + 1/2 + 1/4 + 1/8 + ... tends to 2 when N approaches infinity, the original expression tends to 2N.