Calculate the running time of the code snippet below

Question

for (i=2*n; i>=1; i=i-1)
  for (j=1; j<=i; j=j+1)
    for (k=1; k<=j; k=k*3)
       print(“hello”)

I sopused that its N^5 but Im not sure

Answer 1

Let's try it. The total number of iterations is given by:

$$I=\sum_{i=1}^{2n}\sum_{j=1}^{i}\sum_{k=1}^{\lfloor \log_3(j) \rfloor} 1\approx\sum_{i=1}^{2n}\sum_{j=1}^{i} \log(j) \approx \sum_{i=1}^{2n}\log(i!)\underbrace{\approx}_{\text{Stirling}} \sum_{i=1}^{2n}i\log(i)\underbrace{\approx}_{\text{Sum} \approx \text{Integral}} n^2\log(n) $$

So $O(n^2 \log(n))$, but i'm not so keen on this type of exercise :\