# Similarly structured loops with different big-O time complexities?

I have a function:

int sum = 0;
for (int i = 1; i < n; i*= 2)
for (int j = 0; j < n; j++)
sum++;


From my understanding this is $O(n\log(n))$ because the inner loop runs $n$ times for every time the outer loop runs, and the outer loop is running $\log(n)$ times. Putting them together gives me $O(n\log(n))$, which I understand. However, the following loop:

int sum = 0;
for (int i = n; i > 0; i/= 2)
for (int j = 0; j < i; j++)
sum++;


I see this as $O(n\log(n))$ because the outer loop is running $\log(n) + 1$ times still and the inner loop runs $n + n/2 + n/4...$ whose sum will be some coefficient $c$ times $n$. Together with the outer loop simplifying to $O(n\log(n))$ but it turns out it is actually $O(n)$ however I don't see how it is?

The first version increments sum $$\underbrace{n + n + \dots + n}_{\log n \text{ terms}} = n\log n$$ time; the second does it $$\underbrace{n + \frac{n}{2} + \frac{n}{4} + \dots + 1}_{\log n \text{ terms}} \leq 2n$$ times (use the formula for a geometric series).
By the way, it's not actually wrong to say that the second is also $O(n\log n)$: it's just that you can give a more precise answer of $O(n)$.
• Because, at the final iteration of the outer loop, i=1, so the inner loop executes once, with j=0. – David Richerby Jan 15 '18 at 18:11
In the second algorithm, the total number of increment operations would be $$\sum_{i=0}^{\lceil\lg n\rceil } \frac{n}{2^i}$$, which is $\leq 2n$. See this Wikipedia article about infinit geometric series and the inequallity should be clearer.