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 ?

• mikeyq6: 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).
• Theodore Norvell: I guess k should be initted to 0.
• duplode: i is not equal to 0 or n in the sense used above; it is the loop variable, after all.
• user2228135: yeah..made a mistake...correcting it :) thanks

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

Answer 2

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

enter image description here