¿Cómo resolver este tipo de fórmula de suma?

Question

De alguna manera encontré que la complejidad computacional de un programa es del siguiente orden:

$$O\left (\sum_{i=1}^n\sum_{j=1}^{i^2}\sum_{k=1}^{j^2}k\right)$$

Así que quiero resolver la complicada fórmula en algo como un simple polinomio en términos de n .

Como no tengo formación matemática, me pregunto si hay algún método general/común para resolver este tipo de fórmulas.

Answer 1

La regla general es que si $p(x)$ es un polinomio de grado $d$ entonces $\sum_{m=1}^{n} p(m)$ es un polinomio en $n$ de grado $d+1$ .

Así que $f(j)=\sum_{k=1}^{j^2} k$ es un polinomio de grado $2$ en $j^2$ o un polinomio de grado $4$ en $j$ y $g(i)=\sum_{j=1}^{i^2} f(j)$ es un polinomio de grado $5$ en $i^2$ o un polinomio de grado $10$ en $i$ . Finalmente, $\sum_{i=1}^{n} g(i)$ es un polinomio de grado $11$ en $n$ . Así que lo entiendes:

$$\sum_{i=1}^n\sum_{j=1}^{i^2}\sum_{k=1}^{j^2}k =O(n^{11})$$

Answer 2

Dejemos que $$S_{n} = \sum_{i=1}^{n} \sum_{j=1}^{i^{2}} \sum_{k=1}^{j^{2}} k.$$ Utilizando $$\sum_{k=1}^{j^2} k = \binom{j^2 + 1}{2}$$ entonces $$\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)$$ y finalmente \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} donde $$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.$$

El mayor poder de $S_{n}$ es $\mathcal{O}(S_{n}) \approx n^{11}$ .

Answer 3

Si sólo le interesan las estimaciones del tipo Big-O, puede utilizar $$\sum_{i=1}^N i^r\sim\frac{N^{r+1}}{r+1}$$ o simplemente $$\sum_{i=1}^N i^r=\Theta(N^{r+1}).$$ Entonces $$\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.