Question

3. Analyze the time complexity of the following program segm i = 1; s = 0; while (i<n) { S += i; i *= 2:

Answer 1

while loop depends only on i .

At start i=1 and it  multiplies by 2 every time so i values are

1,2,4,8,16....n since loop runs until i<n

we can write above terms as  $2^{0},2^{1},2^{2},2^{3}........2^{k}$

Now this loop stops when $2^{k}$ =n

Apply logarithm on both sides with base 2 implies

$k=log_{2}n$

Therefore the time complexity of the above program segment is $O(log_{2}n)$

if u understand this upvote else post a comment