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

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$?

-
What have you tried? –  user742 Nov 27 '12 at 11:19
How about running the program. –  Dave Clarke Nov 27 '12 at 11:45
@DaveClarke Running the program just gives the result of a particular input. But a more general proof/formula is needed. –  VISHNU VIVEK Nov 27 '12 at 11:57
Run it on multiple inputs. –  Dave Clarke Nov 27 '12 at 12:16
You should try your best before asking such questions. Try to make a table of i,j value. i starts from n and j starts from 0. In every iteration, write down the value of i and j. for example i=n/2 and j=1. Write i as a function of the previous value. That is, in the next iteration (n/2)/2 ... etc .. until i is less than 0. Does the value of i look anything similar to you ? –  AJed Nov 27 '12 at 13:10

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.

-
It may depend on the particular programming language, but generally, since i=i/2 is written first, the sum should probably begin with $n/2$ instead of $n$ –  Paresh Nov 27 '12 at 13:38
@Paresh it doesnt really matter as we are looking for an upper bound. –  AJed Nov 27 '12 at 13:59
@AJed Aah ... missed that part. –  Paresh Nov 27 '12 at 14:01
@A.Schulz are you sure about log n terms. isn't it log(n)+1 terms –  VISHNU VIVEK Nov 27 '12 at 14:13
@VISHNUVIVEK: Actually it is $\lfloor\log n \rfloor +1$, but these subtleties do not make a difference regarding your question. –  A.Schulz Nov 27 '12 at 14:17

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.

-
those are not float variables.. you've to perform integer division.. in programming, if you don't mention the data-type of a variable, it'll be taken as integer by default –  VISHNU VIVEK Nov 27 '12 at 13:53
check the edit ! –  AJed Nov 27 '12 at 14:04
thanks AJed.. doing that right now.. –  VISHNU VIVEK Nov 27 '12 at 14:09
Actually for any implementation of the variable $i$ which uses a finite number of bits, the loop will terminate. However, even if the loop didn't terminate, you could still answer the question. On every iteration of the loop, $j = \Theta(n)$, and this is not true for any other of the choices. –  Joe Nov 27 '12 at 20:51

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

-
so what you do is taking someone else answer and cite it to yourself ? :) –  AJed Nov 28 '12 at 4:53