Ace dlp

Question

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. Whjch is correct?

a. val(j)=theta(logn)

b. Val(j)= theta(√n)

c. Val(j) = theta(n)

d. Val(j) = theta(nlogn)

Comments

$j=n+\frac{n}{2} +\frac{n}{4}+\frac{n}{8} +\ldots$

Decreasing GP $1+1/2+1/4+1/8+1/16+\ldots =O(1)$

So $val(j)=\theta (n)$

Answer 1

n/2^k=1

n=2^k

k=log2n

ans is A