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$
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$
  • $\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 '18 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$ – David Richerby Jan 15 '18 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, privacy policy and cookie policy

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