[Solved]: How to guess the value of $j$ at the end of the loop?

Problem Detail: 

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

Asked By : Vishnu Vivek

Answered By : Vishnu Vivek

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6952

3.2K people like this

 Download Related Notes/Documents