How to guess the value of $j$ at the end of the loop?

Question

for ( i = n , j = 0 ; i > 0 ; i = i / 2 , j = j + i ) ;

All variables are integers.(i.e. if decimal values occur, consider their floor value)

Let $\text{val}(j)$ denote the value of $j$, after the termination of the loop. Which of the following is true?

(A)$\quad \text{val(j)} = \Theta(\log(n)) $
(B)$\quad \text{val(j)} = \Theta(\sqrt n) $
(C)$\quad \text{val(j)} = \Theta(n) $
(D)$\quad \text{val(j)} = \Theta(\log\log n) $

Please explain, is there any easy way to guess the value of $j$?

Answer 1

If you unfold the loop you get:

$$\text{val}( j)=n+n/2+n/4+ n/8 \ldots$$

In total you have $\log n$ terms. See this post, how to evaluate the sum.

Answer 2

In theoretical processor, this loops never ends. Dividing $i$ by 2 repetitively will always lead to i > 0. [This has been changed in the Q. description] Therefore:

$ j = n + n/2 + n/4 ... $

$ j = \sum _{i = 0} ^{\inf} n (1/2)^{i}= n \sum _{i = 0} ^{\inf} (1/2)^{i}$

Given that $\sum _{i = 1} ^{\inf} c^i = c / (1 - c) $ then the solution of this equation is $j = 2 n$

In your integer program, follow the link posted by @A.Schulz. -- If you compute the geometric series provided, it will end up to the same approximate result. so you guess your answer.

More details:

given that $\sum _{i = 0} ^{\log n} (1/2)^i = \frac{(1/2)^{\log n + 1} - 1}{(1/2) - 1} = 2( 1 - 1/2n) = 2 - 1/n $

Then, the final result is $n (2 - 1/n) = 2n - 1$ . Therefore, it is C.

Answer 3

Lets break the loop as

j = 0; 
for ( i = n ; i > 0 ; i = i/2 ) 
     j = j + i ;

Since the input size decreases by half, the total number of iterations would be $\log(n)+1 $

As $i$ becomes $n, n/2 , n/4 \ldots$ up to $\log(n)+1 $ terms, the corresponding $j$ value gets added.

So, $val(j) = n+n/2+n/4+n/8+\ldots n/2^{\log(n)} $

$val(j) = n ( 1 + 1/2+1/4+1/8+\ldots 1/2^{\log(n)})$

Performing sum of geometric series,

$S_n = \frac{1 - (1/2)^{\log(n)}}{1 - (1/2)} $

We know that $a^{\log(b)} = b^{\log(a)}$

Thus $2^{\log(n)} = n^{\log(2)} = n$

$S_n = \frac{2(n-1)}{n}$

$val(j) = n\frac{2(n-1)}{n}$

$val(j) = 2(n-1)$

Thus, $val(j) = \Theta(n)$