2
$\begingroup$

I used the search function and a good amount of google searches, but wasn't able to get a straight answer on how a loop of the form below, is translated to a proper summation where the function derived from the summation is: $O(\log n)$.

Example of the for loop:

int j = 0;
for (int i = 2; i <= n; i *= 2) {
    j = j + n * 2;
}

So I understand within the loop we have 3 operations (multiplication, addition, then assignment).

I understand that the index $i$ ranges from $[1, 2, 4, 8, 16, 32, 64, 128, 256]$... ($i$ is only equal to powers of 2, up to $n$).

So essentially the range of $i$ seems to be from $[2^m, n]$ and $m \in [0, \log_2n]$ right?

Also, $i^m < n$ so the loop executes $\log_2n - 0 + 1 = \log_2n + 1$ times right? How do we go about expressing this in summation notation?

Is it this (just taking a guess, not sure if it's right):

$$\sum\limits_{i = 0}^{log_2n + 1} 3$$ since we have 3 operations? If this is the answer, why do we keep the upper bound of the summation to $\log_2n$ instead of $n$? Also, I know typically we'd use $\log n$ but just put in the base 2 to help clear things up in my own head.

Could someone please show how the summation of the for loop is properly written?

$\endgroup$
1
$\begingroup$

Assuming the model of computation is RAM(Random Access Machine). Which means the cost of addition, multiplication,division etc is constant. Now your program is

int j = 0;
for (int i = 1; i <= n; i *= 2) {
    j = j + n * 2;
}

Inside the loop, you are doing addition, multiplication, comparison etc which takes constant time. Let $k$ denotes the number of iterations of the loop. Let $c_i$ denotes the cost at $i$th iteration of loop. The total cost is

$$ = c_1+c_2+\ldots + c_{k}$$ $$ = \sum_{ j =1 \text{ to } k}c_i$$

It is easy to see that above summation gives $\mathcal{O}(\log n)$.

$\endgroup$
  • 1
    $\begingroup$ Okay, thank you. Yes you are correct in assuming the model of computation is RAM, and the cost of those operations is constant. Sorry, I had $i = 1$ when it should be $i = 2$. I'm going to edit that now. Given that, would it be fair to say that the summation is: $$\sum\limits_{i = 0}^{[\log n]} c_i $$ where I used [ ] to denote floor division (in the event that $n$ is not even) so this shows that the loop runs at most $\log n$ times? $\endgroup$ – quantitative_ Jan 21 at 17:12

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.