Time complexity of following code

The answer is o(N) but I think answer should be o(n*log(N)).Please help.

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

loops will iterate roughly n times so it can be said as O(N).

1 Like

For the 1st iteration of the outer loop, the inner loop runs from j=0 to j=N-1, that is N times. Similarly for the 2nd iteration of the outer loop, the inner loop runs N/2 times.
Therefore, the inner loop runs for a total of
N + N/2 + N/4 + … times
Since this forms an infinite GP series, the inner loop runs for a total of N/(1-1/2), that is 2N times, giving you an order of growth of O(N).

6 Likes

outer loop have time comlex of log(n) as i =i/2 (getting halved)not i++ so how it can be n ??

but outer loop should run log(n) times as i is getting halved ,it is not i++???
[/quote]

You can say this is O(N*log(log(N))).

P.S - Correct me if I am wrong.

1 Like

O(N\times \log(\log N)) is an upper bound for the code, but O(N) is tighter and, so, better :slight_smile:

@ayush29azad: @saarthak_1607 has given the correct answer, but here is more detail: “GP” is “Geometric Progression”, and the sum he has provided is a well-known one.

4 Likes

thank you ,now i have understood ;