retagged by
1,775 views
0 votes
0 votes

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("*");
      }
   }
}
retagged by

2 Answers

Best answer
4 votes
4 votes

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

selected by
0 votes
0 votes
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 )
edited by

Related questions

1 votes
1 votes
2 answers
1
Apeksha asked Aug 6, 2016
738 views
for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) for(l=1;l<=k;l++) printf("gate");
0 votes
0 votes
2 answers
2
kalpashri asked May 12, 2015
553 views
for(i=1;i<=n;i=i*2);for(j=1;j<=i;j=j+1);{}