CODEWITHSUNDEEP
time-complexitybig-ocomplexity-theory
Mr. J
Mr. J

Reputation: 66

What is the Big-O of this nested loop?

int z=1; 
for（int i=0;i*i<n;i++）｛
  z*=3;
  for（int j=0;j<z;j++）{
   // Some code
  }
}

Answer is O(3^n). Is it correct? How to figure out time complexity of nested loop?

Upvotes: 1

Views: 106

Answers (2)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

You could approach the problem using Sigma notation this way:

enter image description here

Upvotes: 1

softwarenewbie7331
softwarenewbie7331

Reputation: 967

outer loop: i goes from 1 to sqrt(n); inner loop: j,z goes up to 3^(sqrt(n));

"some code" will run 1 + 3 + 3^2 + ... + 3^(sqrt(n)) times

let sum = 1 + 3 + 3^2 + ... + 3^(sqrt(n))
sum - 3*sum = 1 - 3(sqrt(n) + 1)
sum = 1 - 3(sqrt(n) + 1) / (1-3) = 2( 3^(sqrt(n)+1) - 1 )

2( 3^(sqrt(n)+1) - 1 ) << O( 3^sqrt(n) )

O(3^sqrt(n)) is more accurate

Upvotes: 1

Related Questions