How to resolve this kind of summation formula? I somehow found a computing complexity of a program is of the following order:
$$O\left (\sum_{i=1}^n\sum_{j=1}^{i^2}\sum_{k=1}^{j^2}k\right)$$
So I want to resolve the complicated formula into something like a simple polynomial in terms of n.
As I am not from a math background, I wonder if there is any general / common method to resolve such kind of formula?
 A: Let 
$$S_{n} = \sum_{i=1}^{n} \sum_{j=1}^{i^{2}} \sum_{k=1}^{j^{2}} k.$$
Using 
$$\sum_{k=1}^{j^2} k = \binom{j^2 + 1}{2}$$
then
$$\sum_{j=1}^{i^{2}} \binom{j^2 + 1}{2} = \sum_{j=1}^{i^2} \frac{j^{4} + j^{2}}{2} = \frac{1}{60} \, i^{2} \, (i^{2} + 1) \, (2 \, i^{2} + 1) \, (3 \, i^{4} + 3 \, i^{2} + 4)$$
and finally
\begin{align}
S_{n} &= \frac{1}{60} \, \sum_{i=1}^{n}  i^{2} \, (i^{2} + 1) \, (2 \, i^{2} + 1) \, (3 \, i^{4} + 3 \, i^{2} + 4) \\
&= \frac{1}{60 \cdot 462} \, n \, (n+1) \, (2n+1) \, P_{n},
\end{align}
where 
$$P_{n} = 126 \, n^8 + 504 \, n^7 + 721 \, n^6 + 399 \, n^5 + 526 \, n^4 + 975 \, n^3 + 700 \, n^2 + 195 \, n + 243.$$
The highest power of $S_{n}$ is $\mathcal{O}(S_{n}) \approx n^{11}$.
A: If you only care about big-O type estimates, then you can use
$$\sum_{i=1}^N i^r\sim\frac{N^{r+1}}{r+1}$$
or just
$$\sum_{i=1}^N i^r=\Theta(N^{r+1}).$$
Then
$$\sum_{k=1}^{j^2} k=\Theta(j^4),$$
$$\sum_{j=1}^{i^2}\sum_{k=1}^{j^2} k=\sum_{j=1}^{i^2}\Theta\left(j^4\right)
=\Theta(i^{10})$$
etc.
A: The general rule is that if $p(x)$ is a polynomial of degree $d$ then $\sum_{m=1}^{n} p(m)$ is a polynomial in $n$ of degree $d+1$.
So $f(j)=\sum_{k=1}^{j^2} k$ is a polynomial of degree $2$ in $j^2$, or a polynomial of degree $4$ in $j$, and $g(i)=\sum_{j=1}^{i^2} f(j)$ is a polynomial of degree $5$ in $i^2$, or a polynomial of degree $10$ in $i$. Finally, $\sum_{i=1}^{n} g(i)$ is a polynomial of degree $11$ in $n$. So you get that:
$$\sum_{i=1}^n\sum_{j=1}^{i^2}\sum_{k=1}^{j^2}k =O(n^{11})$$
