why the time complexity is O(n) not O(nlogn)?

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

then this function should give O(nlogn).

since outer loop run O(logn) time

inner loop O(n) time 

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

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 2

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 3

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 ?