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

One of the common mistakes of people when they approach to these tasks are looking at things as "straightforward", But this is not the case on many scenarios (like this one).

The right way to figure out the time complexity (also in memory complexity) is trying to "follow" the steps of calculation the program will execute and how much time each step will take.

I would recommend writing down what will happen at the first 5+- iterations and try to see what is the pattern.

So, in this case, the first loop is gonna start from N until 0 while the index is reduced by half each iteration. You were right that it implies for O(log(N)), but lets write the index down for some of the first iterations:

i=N
i=N/2
i=N/4
i=N/8
i=N/16
...

Now, the real thing happens in the second for which inside the first loop. First, you can see that the second index j has a dependency with i which should immediately raise a red flag and we should pay special attention to it. The second loop goes from 0 to i of the current iteration with increment of one. At first, you would probably say it is O(n) because the change is an increment of one and it goes from 0 to a specific known integer. But since that integer is dynamically change, you can't really say that, and you must know what i is gonna be. So lets write the first iterations of the inner loop for each of the iterations above:

i=N       ->  |  j=0  |  j=1  |  j=2  | ... |  j=N    |
i=N/2     ->  |  j=0  |  j=1  |  j=2  | ... |  j=N/2  |
i=N/4     ->  |  j=0  |  j=1  |  j=2  | ... |  j=N/4  |
i=N/8     ->  |  j=0  |  j=1  |  j=2  | ... |  j=N/8  |
i=N/16    ->  |  j=0  |  j=1  |  j=2  | ... |  j=N/16 |
...

Now, each "box" (| |) I wrote above is a step the program executes. As I said before, we need to know also how much time each step is gonna take. In this case, each step (each iteration) includes one operation of variable (count) increment, which we consider as O(1) (a constant).

The last thing we should do is to sum up all the steps we mentioned above with their costs:

First row will run N times (0,1,2,..,N) - each time the step will cost O(1). -> So it's going to be N*1 = N Second row will run N/2 times (0,1,2,..,N/2) - each time the step will cost O(1). -> So it's going to be (N/2)*1 = N/2 Third row will run N/4 times (0,1,2,..,N/4) - each time the step will cost O(1). -> So it's going to be (N/4)*1 = N/4 And so on..

When we sum it up, the program cost will be: N+(N/2)+(N/4)+(N/8)+...+~(N/N) = N * ( 1 + (1/2) + (1/4) + (1/8) +... ) ( 1 + (1/2) + (1/4) + (1/8) +... ) is a simple known math series. (You can get help from some websites or little google search to learn the results of those or more complicated series). This one Equals to 2-(2/N) at most.

So the final cost will be: N * ( 2 - (2/N) ) = 2N - 2 which is O(N) overall.

This answer is pretty long and well detailed for this question but I was trying to show a "way of thinking" more than just solving the problem. I hope it helped you (and others) to think different on questions like these, Trying to take each loop and each step and check carefully how many steps are going to happen here and more importantly (and mostly forgotten) what is the cost of each step.

Answer 2

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.

Answer 3

For a input integer n, the innermost statement is executed following times.

n + n/2 + n/4 + … 1

So time complexity T(n) can be written as

T(n) = O(n + n/2 + n/4 + … 1) = O(n)

you may refer this : Link

Answer 4

The second for-loop while be executed N + N/2 + N/4 +....+ N/N

, the first for-loop decides how much the second for-loop will be executed.

When i = 0, j loops until N

, i = N/2, j loops until N/2

, And so on

, The Big O notation of N + N/2 + N/4 +....+ N/N will be O(N)

Answer 5

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 6

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)