Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
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$?

share|improve this question
1  
What have you tried? –  user742 Nov 27 '12 at 11:19
1  
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
1  
Run it on multiple inputs. –  Dave Clarke Nov 27 '12 at 12:16
1  
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

3 Answers 3

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.

share|improve this answer
    
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.

share|improve this answer
    
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
up vote 0 down vote accepted

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

share|improve this answer
2  
so what you do is taking someone else answer and cite it to yourself ? :) –  AJed Nov 28 '12 at 4:53
1  
oh sorry AJed! I didn't see your answer after you made your last edit. I was actually having problems in finding the sum of geometric series. And furthermore, though asymptotically your answer is correct, it has minor glitches. Since the answer is asked in tight bound, even a minor error can cause major deviation in the result. But thank you so much for your answer.. Now I can confirm that I'm in the right direction and that my answer is correct –  VISHNU VIVEK Nov 28 '12 at 6:55
    
see also math.stackexchange.com/questions/244817 You should give credit to the people that helped you to come up with "your" answer. –  A.Schulz Nov 29 '12 at 17:21
    
@A.Schulz lol..actually that question was also asked by me :) Thanks anyways!! –  VISHNU VIVEK Dec 1 '12 at 0:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.