CODEWITHSUNDEEP
big-otime-complexity
user2228135
user2228135

Reputation: 239

Time complexity of nested for loop?

This question is for revision from a past test paper just wondering if i am doing it right.

im new to this, so im having a bit of difficulty with more complicated questions. this is one of them...

If anyone could elaborate on this, i'll be very grateful... So i have to find out the complexity of this piece of code...

cout = 0;
for(int i=1 ; i<=n ; i*=3)
   for(int j=1 ; j<=i; j++)
      for(int k=1 ; k<=n ; k++)
          count++;

so, i tried doing it...and i got O(n^2logn).. its not correct...the answer should be O(n^2).. can somebody help me on this ?

Upvotes: 1

Views: 116

Answers (2)

Mohamed Ennahdi El Idrissi
Mohamed Ennahdi El Idrissi

Reputation: 2977

A formal manner to determine the time complexity of your algorithm:

enter image description here

Upvotes: 1

Theodore Norvell
Theodore Norvell

Reputation: 16221

The number of iterations of the second loop is $$ 1 + 3 + 9 + ... + m $$ where $m$ is roughly $n$. This sums to $\Theta(n)$. Then the innermost loop is another factor of Theta(n). So $\Theta(n^2)$.

Upvotes: 1

Related Questions