TIME COMPLEXITY

Question

int fun(int n)
{
    int count=0;
    for(int i=n; i>0; i/=2)
    for(int j=0; j<i; j++)
      count += 1;
    return count ;
}

Answer 1

Outer loop runs $\log_2 n$ times.

For $i = n$, inner loop runs $n$ times.

For $i = n/2$, inner loop runs $n/2$ times.

$\vdots$

For $i = 1$, inner loop runs $1$ time.

So, overall, the inner loop runs for

$T(n) = 1+2+4+8+ \cdots + n$ times.

This is a Geometric Progression, which can be written as:

$T(n) = 1+2+4+8+\cdots+n = 2n-1 = \mathcal{O}(n)$

Hence, option C is correct.

Answer 2

The outer loop iteration variable i is halved in each iteration. The inner loop will execute i times for each iteration of the outer loop. So, the

count += 1;

statement, which is the most repeated one and hence the one contributing to time complexity will be done

n + n/2 + n/4 + .... 1 times, which is a GP and we can approximate it as an infinite GP, so the summation will be a/(1-r), where a is the first term and r is the common ratio.

n/(1-1/2) = 2n = O(n)

Answer 3

 for(int i=n; i>0; i/=2) -------------L1
    for(int j=0; j<i; j++)------------L2

L1 stops when (n/2^k=1)

                        or k=log₂n 

L2 iterrates total = n + n/2 + n/2² + ... + n/2^log₂n    (for log₂n time) (it is finite series)

                        =n 1. ( (1- 1/2^log₂n)/(1-1/2))

                        =n x ( (1-1/n) / (1/2) )

                         = 2n-2

So it is O(n) ...