Geeks - Doubt closed

Question

What is time complexity of fun()?

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

(A) O(n^2)
(B) O(nLogn)
(C) O(n)
(D) O(nLognLogn)

Comments

Isn't its answer have to be nlogn.

---

is it O(n)?

---

How?

---

yes O(n)

---

If we solve it, it will be like ( n + n/2 + n/4 + ........) Take n outside and the remaining series will lead to logn.
so isn't the answer has to be nlogn.

---

simply unroll the dependency..

when i=n ,j will run n times

i=n/2, j will run n/2 times

i=n/4, j=n/4

i=n/8,j=n/8

-----------------------

Total Complexity = n + n/2 + n/4 + n/8 .............. = n(1 + 1/2 +1/4 + 1/8............ logn times) = O(n)

(1 + 1/2 +1/4 + 1/8............ logn times) this value will be nearly 1.

---

what is the equation of log n.

---

i think you got it

Answer 1

in this problem ...how many times for loop will execute:

       first time loop:  n times

      second time :   n/2 times

        similarly  form series   =    n +n/2 +n/4 + .....+1

                 its decreasing GP series

      TC =   O(n)

Hence option C is correct