Time Complexity: O(logN) or O(N)?

Question

I thought the time complexity of the following code is O(log N), but the answer says it's `O(N)`. I wonder why: ``` int count = 0; for (int i = N; i > 0; i /= 2) { for (int j = 0; j < i; j++) { count += 1; } } ``` For the inners for-loop, it runs for this many times: `N + N/2 + N/4 ...` it seems to be `logN` to me. Please help me understand why here. Thanks

Accepted Answer

1, 1/2, 1/4, 1/8... 1/2 ** n is a geometric sequence with a = 1, r = 1/2 (a is the first term, and r is the common ratio).

Its sum can be calculated using the following formula:

In this case, the limit of the sum is 2, so:

```
n + n/2 + n/4 ... = n(1 + 1/2 + 1/4...) -> n * 2
```

Thus the complicity is O(N)

Time Complexity: O(logN) or O(N)?

Solution

Problem