# What is the time complexity (in Θ-notation) in terms of n?

Consider the following algorithm, where $n$ is a parameter.

sum = 0 ;
for ( i = 0 ; i < n ; i++ )
for ( j = 1 ; j <  n^3 ; j = 3*j )
sum++ ;

What is the time complexity (in $\Theta$-notation) in terms of n?

So far, this is what I've done: The running time is $\Theta (N^4)$ Because the for loop’s condition is depend on $n$ and is incremented by $1$, and then inside running time is $O(1)$. I feel i'm wrong here. Any help would be appreciated.

• I edited your post and assumed that 'n3' should have been 'n^3'. Feel free to correct it if it means something else. – punctured dusk Jun 6 '14 at 18:29
• Voted to reopen--showing your work is good. :) Regarding your answer--you're close, but the inner for loop does not increment j by $1$ each iteration. – apnorton Jun 7 '14 at 2:17

The inner loop runs in $\Theta(\log_3(n^3))$ because we can multiple $j=1$ by $3$, $\log_3(n^3)$ times before $j$ is greater than $n^3$. The outer loop executes exactly $n$ times. So we get $\Theta(n\log_3(n^3))$ which we can simplify to $\Theta(n\cdot 3\cdot\log(n))= \Theta(n\log(n))$.