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?