Time complexity of the nested for loop function

Question

What is the time complexity of the following function:

 

function(n) {
   for(i = 0; i < n; i = i*2) {
      for(j = 0; j < i; j++) {
          printf("*");
      }
   }
}

Comments

i think zero times ???

Answer 1

Value of i always remains 0 hence it gets trapped in outer loop indefinitely, irrespective of the values of n.

That means, it doesn't depend on the input.

Therefore, it's time complexity is O(1).

Comments

function(n) {
   for(i = 1; i < n; i = i*2) {
      for(j = 0; j < i; j++) {
          printf("*");
      }
   }
}

what will be the time complexity?

---

O(n) 

Values of i will be power of 2, and the inner loop will run power of 2 times.

T(n) = $2^{0} + 2^{1} + ... + 2^{k}$ , where k = $\log n$ (base 2)

since it is a geometric series

T(n) = $2^{k+1} - 1$

T(n) = 2.n - 1

T(n) = O(n)

---

O(n)

Answer 2

if i=0 is replaced by 1 then inner loop will execute 1,2,4,8,16,32 ...log2n times so total no of times =2^logn-1/2-1=>O(2^log n)=>0(n )

Comments

i is getting multiplied by 2 and initially i is 0 so each time it will be 0 only and j<i will not be true. so printf will not execute once also.

---

oh yes then it seems to be incorrect or tricky question