The order of growth analysis for simple loop

Question

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

Answer 1

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

Answer 2

The first loop runs $\log_2N$ times but in nested loops we are interested in the running time of the inner loop (thanks to Tsuyoshi Ito for the clarification). The second loop depends on the value of $n$ in the first. When $n=N$, the second loop runs $N$ times, when $N$ is halved it runs $\frac{N}{2}$ times and so on. The second loop runs in total: $N + \frac{N}{2} + \frac{N}{4} + \dots +1=N(1+\frac{1}{2}+\frac{1}{4}+\dots+\frac{1}{2^{k}})\approx N$. So the running time is $\Theta(N)$.