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;
}
}
```

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

@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 ;