Multiple choice

Consider the following C-program fragment in which i, j and n are integer variables.
for( i = n, j = 0; i > 0; i /= 2, j +=i ); Let val ( j ) denote the value stored in the variable j after termination of the for loop. Which one of the following is true?

  1. $val(j)=\Theta(\log n)$
  2. $val(j)=\Theta (\sqrt{n})$
  3. $val(j)=\Theta( n)$
  4. $val(j)=\Theta (n\log n)$
Reveal answer Fill a bubble to check yourself
C Correct answer
Explanation

$j = n/2+n/4+n/2+\ldots +1$

number of iteration will be $2^k = n$ or $k = \log n$

this is in GP find sum till $\log n $,= $\Theta(n)$

Keep practicing — related questions