in Algorithms retagged by
163 views
0 votes
0 votes
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)
in Algorithms retagged by
163 views

1 comment

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

1 Answer

0 votes
0 votes
n/2^k=1

n=2^k

k=log2n

ans is A

Related questions

1 vote
1 vote
0 answers
3