Time complexity function in terms of theta notation

Question

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 $\mathcal{O}(1)$. i feel i'm wrong here. any help would be appreciated.

Answer 1

Here's a hint: We're not $incrementing$ the iterator of the second for loop, we're scaling it my $3$. So the number of iterations of the second for loop equals $\lceil \log_3(n^3)\rceil = \lceil 3\log_3(n)\rceil \in \Theta(\lg n)$. For example, take $n = 15$. What's the least $j \in \mathbb{N}$ so that $3^j \ge 15^3=3375$? You can verify that this is $\lceil \log_3(15^3) \rceil = 8$.