Runtime-Analysis for single loop incremented by a factor of 3

Question

So, I'm trying to understand how to get the run time of this loop:

for(int i = 1; i < n*n*n; i*=3) {...}

So, far I know:

• loop starts at 1
• finishes when $i > n^3-1$
• that $i$ is multiplied by 3 each iteration.

Intuitively it seems like as $n$ gets larger the number of iterations decreases which makes me think that the run-time is $O(log$ $n)$. My question is if this is correct if it is what is a mathematical way I could derive that answer?

Answer 1

That's right. This for loop stops when: $$ 3^i < n^3 \rightarrow i<3\log(n) $$ Which implies the complexity of this for loop is $O(\log(n))$.