Time complexity of nested for loop?

Question

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 ?

I would have thought it would be O(n^3). When i=0, then the complexity is O(n^2), but then when i=n, the complexity is O(n^3). — mikeyq6
– mikeyq6, Commented Nov 6, 2013 at 18:27
i is not equal to 0 or n in the sense used above; it is the loop variable, after all. — duplode
– duplode, Commented Nov 6, 2013 at 18:30

Theodore Norvell · Accepted Answer · 2013-11-06 18:33:45Z

1

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

answered Nov 6, 2013 at 18:33

Theodore Norvell

16.4k7 gold badges35 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Mohamed Ennahdi El Idrissi · Accepted Answer · 2014-03-14 23:55:10Z

1

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

enter image description here

answered Mar 14, 2014 at 23:55

Mohamed Ennahdi El Idrissi

2,9872 gold badges21 silver badges35 bronze badges

Collectives™ on Stack Overflow

Time complexity of nested for loop?

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related