3
$\begingroup$

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

| cite | improve this question | |
$\endgroup$
  • 1
    $\begingroup$ There are plenty of questions discussing the complexity of (nested) loops, e.g. here, here, here and here. Please check those and get back to us with specific problems you face. $\endgroup$ – Raphael♦ Sep 29 '12 at 21:06
8
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ (1) The last sentence of the answer is still incorrect. You multiplied the total time of the inner loop by the number of iterations of the outer loop, but that is not correct. (2) For a complete answer, the assumption that N is a power of two has to be justified. $\endgroup$ – Tsuyoshi Ito Sep 30 '12 at 14:17
  • $\begingroup$ The previous comment of mine referred to revision 3. In revision 4, you changed Θ(…) to O(…), so the last sentence itself is no longer incorrect, but it is a loose bound. I guess that the question is asking the tight bound up to a constant factor, so your answer still does not answer the question correctly. $\endgroup$ – Tsuyoshi Ito Sep 30 '12 at 14:21
  • $\begingroup$ @TsuyoshiIto Should we not multiply the running times of loops when they are nested? $\endgroup$ – mrk Sep 30 '12 at 14:23
  • $\begingroup$ @saadtaame: If you perform 100 tasks each of which takes 10 seconds, then multiplying these two numbers is correct. But if you perform 100 tasks which take 10 seconds in total, it is not meaningful to multiply 10 by 100. $\endgroup$ – Tsuyoshi Ito Sep 30 '12 at 14:26
  • $\begingroup$ $\approx N$ is a bit of a stretch; it's $\approx 2N$, rather. And towards $\Theta$, you need that the sum is $\leq 2N$ and $\geq N$. $\endgroup$ – Raphael♦ Sep 30 '12 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy