Similarly structured loops with different big-O time complexities?

Question

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?

Answer 1

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)$.

Answer 2

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.