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

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

Your Answer

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