How to resolve this kind of summation formula?

Question

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?

Answer 1

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})$$

Answer 2

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.

Answer 3

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}$.