The order of growth analysis for simple loop

What would the order of growth for this loop be:

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

The first loop seems to run for $\log N + 1$ times and the second loop runs $n$ times.

So is the correct answer $O(n \log n)$?

When the iterations of the inner loop depend on the outer loop, it's better to sum over the amount of iterations of the inner loop. There is no need to overcomplicate this and think of logarithms just because the outer loop has logarithmic behavior.

Iterations

In this example, we can see the number of iteration the inner loop performs is halved in each step of the outer loop:

• $N$ iterations of the inner loop

• $\frac{N}{2}$ iterations

• $\frac{N}{4}$ iterations

• $\dots$

• $\frac{N}{2^i}$ iterations

• $\dots$

• 1 iteration

as the outer loop iterates.

Formalizing

Factoring $N$, we get:
$$ N(1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{N})$$

Knowing that:
$$\sum_{i=0}^\infty \frac{1}{2^i} = 1 + \frac{1}{2}+ \frac{1}{4}+ \frac{1}{8}+\cdots = 2$$

we can conclude that:

$$ N(1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{N}) < 2N$$

Which is why the algorithm's complexity is bounded by $\mathcal{O}(N)$

Since the algorithm performs at least $N$ steps (assuming $N \geq 1$), it follows that the runtime behavior is also described by $\Omega(N)$, which implies that it is in $\Theta(N)$

StackExchange Computer Science Q#4800, answer score: 8