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 ;
}

Comments

I think you are correct. Ans should be (n log n).

Because here j runs for i times.

So T(n) = n + n/2 +n/4 + ...... +1

              = O(n log n )

---

According me and you the answer is O(nLogn).

But the correct answer is O(n).

---

Ref here:https://gateoverflow.in/4543/time-complexity

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) ...

Answer 4

The correct answer indeed will be $ O(N) $. 

Here is the explanation, Let consider $ N = 2^K $

then the outer loop will run up to $ (Log N) $ times.

Then total work done by the program can be represented as,

T(n) = $ \sum_{i=0}^{log N} \frac{N}{2^i} $

T(n) = $ \sum_{i=0}^{log N} \frac{2^K}{2^i} $         (We have considered $ N = 2^{K} $ )

T(n) = $ \sum_{i=0}^{log N} 2^{K-i} $ 

T(n) <= $ \sum_{i=0}^{log N} 2^{K} $ 

T(n) <= $ 2^{K+1} $

T(n) <= $ 2^{log N+1} $

 

T(n) = $ O(2N) $.

 

Hence Time complexity of the program is O(N).

 

Answer 5

O(n) or o(n)can not  definitely place upper bound  n+n/2+n/4+n/8+ .....1

hence ans can be O(nlogn)

Answer 6

See here T(n)=n+n/2+n/4+n/6+.............................logn term

                      =n(1+1/2+1/4+1/6+.....................1/2^logn-1)

Let n=a^k

T(n)=a^k(1+1/2+1/4+1/6+..................1/2^k-1)       .................(1)

Now solve decreasing GP=1+1/2+1/4+1/6+.....................1/2^k-1

Here a=1 , r=1/2

S=a(1-r)ⁿ/1-r

  =(1-(1/2)^k)/(1-1/2)

  =2(1-1/2^k)

Now From Equation (1)....

T(n)=2a^k(1-1/2^k)

Since n=a^k  SO,

T(n)=2n(1-1/2^logn)

       =2n(1-1/n^log2)

So T(n)=O(n)

Comments

Check this:

http://math.stackexchange.com/questions/1476543/why-is-time-complexity-of-fun-on

---

@Mukesh sharma why i need to check .Here you can see T(n)=O(n).

Is there any mistake then  i would i like know ?