0
$\begingroup$

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?

$\endgroup$

2 Answers 2

0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Why is the last term 1 in the second summation? Also, could you please explain how the sum equals 2n in a bit more detail? $\endgroup$
    – TheShield
    Jan 15, 2018 at 18:08
  • $\begingroup$ Because, at the final iteration of the outer loop, i=1, so the inner loop executes once, with j=0. $\endgroup$ Jan 15, 2018 at 18:11
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.