Given algorithm, Whats the time complexity of it?

Question

Given algorithm:

The inner loop is:

And the outer loop is: $\frac{n(n+1)}{2} * n$ but in the answer is says that I don't need to multiply it by $n$. Can anyone explain why the series is enough for the two outer for loops?

Answer 1

Outer loop complexity: $$\sum_{i=1}^n\sum_{j=1}^i1=\sum_{i=1}^ni=\frac{n(n+1)}{2}$$

Answer 2

The innermost loop takes $O(\log \log n)$ time. You seem to understand that already. Now the outer two loops perform the innermost loop $O(n^2)$ times, as you can check by computing $\sum_{i=1}^n i = \frac{n(n+1)}{2}$. Thus the whole thing takes $O(n^2 \log \log n)$ time.