Calculate the complexity of an algorithm
The number of times that the if is executed is
$$
\sum_{i=1}^{n-1} (i^2-1) = \Theta(n^3).
$$
The number of times that sum is incremented is
$$
\sum_{i=1}^{n-1} \sum_{\substack{1 \leq j &lt; i^2 \\ i \mid j}} j =
\sum_{i=1}^{n-1} \sum_{k=1}^{i-1} ki = \sum_{i=1}^{n-1} i \binom{i}{2} = \Theta(n^4).
$$
Altogether, we get a running time of $\Theta(n^4)$.