Analyze for loop with if statement I have this rather complicated loop:
sum=0
for i=1 to n do
    for j=1 to i^2 do
        if(j (mod i) = 0) then
            for k=1 to j do
                sum++

How the heck do I analyze this? I would try to use a sum but the if statement throws me off. How can I determine what time this nested for loop runs in?
 A: The code is essentially this:
sum=0
for i=1 to n do
    for j=1 to i do
        for k=1 to j^2 do
           sum++

The $ k $ loop executes $ j^2 $ times. 
The $ j $ loop executes $ i $ times
Therefore the time taken to execute all the iterations of a $ j $ loop is
$ \sum\limits_{j = 1}^{i}{j^2} = O(i^3) $
Finally, the $ i $ loop executes $ n $ times, the time taken to execute the whole program will be
$ \sum\limits_{i = 1}^{n}{O(i^3)} = O(n^4) $.
That's all.
A: sum=0
for i=1 to n do
    for j=1 to i^2 do
        if(j (mod i) = 0) then
            for k=1 to j do
                sum++

This is the same as
$$\begin{align}
%
S(n) &= \sum_{i = 1}^n \sum_{\begin{array} {l} j = 1 \\ j \equiv 0 \pmod i \end{array}}^{i^2} \sum_{k = 1}^j 1
%
\\ \\ & \text{Let } m = j/i
%
\\ \\ &= \sum_{i = 1}^n \sum_{m = 1}^{i} \sum_{k = 1}^{m^2} 1
%
\end{align}$$
You don't have to evaluate the sum exactly, all you need to be able to determine is that $\sum_{i = 1}^n \sum_{m = 1}^{i} \sum_{k = 1}^{m^2} 1$ is a 4th degree polynomial.
$$\begin{align}
%
S(n) &= \sum_{i = 1}^n \sum_{m = 1}^{i} m^2
%
\\ \\ &= \sum_{i = 1}^n A~i^3 + \dots
%
\\ \\ &= A~n^4 + \dots 
%
\end{align}$$
Since an increment takes a logarithmic amount of time to compute, your runtime is
$$\begin{align}
%
R(n) & \in O(S(n)\log(S(n))
%
\\ \\ &= O(~ (A~n^4 + \dots) \log( An^4 + \dots)~)
%
\\ \\ &= O(n^4\log(n))
%
\end{align}$$

The exact computation, which isn't necessary but might help understand, is:
$$\begin{align}
%
S(n) &= \sum_{i = 1}^n \sum_{m = 1}^{i} m^2
%
\\ \\ &= \sum_{i = 1}^n \frac{1}{6}\bigg(2i^3 + 3i^2 + i\bigg)
%
\\ \\ &= \frac{1}{12} \bigg(n^4 + 4n^3 + 5n^2 + 2n\bigg)
%
\end{align}$$
