Cómo calcular la complejidad temporal de un triple bucle anidado representado por $\sum_{i=1}^{2n} \sum_{j=1}^{n} \sum_{k=j}^{n} i-j$

Question

var r = 0;
for(var i=1; i<=2*n; i++) {
  for(var j=1; j<=n; j++) {
    for(var k=j; k<=n; k++) {
      r = r + (i - j);
    }
  }
}

Estoy intentando usar la suma para resolverlo, pero tengo un poco de problemas.

Tengo este resumen:

$$ \sum_{i=1}^{2n} \sum_{j=1}^{n} \sum_{k=j}^{n} i-j $$

Pero después de intentar obtener una forma cerrada para esto, obtuve $-n^4 + n^2$ que seguramente no es la respuesta.

¿Podrían ayudarme?

Answer 1

$$\sum_{i=1}^{2n} \sum_{j=1}^{n} \sum_{k=j}^{n} i-j$$ $$\sum_{i=1}^{2n} \sum_{j=1}^{n} (i-j)\cdot(n-j+1)$$ $$\sum_{i=1}^{2n} \sum_{j=1}^{n} (ni-ij+i-nj+j^2-j)$$ $$\sum_{i=1}^{2n} (ni\cdot n-i\frac{n(n+1)}{2}+in-n\frac{n(n+1)}{2}+\frac{n(n+1)(2n+1)}{6}-\frac{n(n+1)}{2})$$ $$\sum_{i=1}^{2n} \left(i( n^2-\frac{n(n+1)}{2}+n)-\frac{n(n^2+3n+2)}{6}\right)$$

$$\sum_{i=1}^{2n} \left(i\frac{n(n+1)}{2}-\frac{n(n^2+3n+2)}{6}\right)$$ $$ \frac{2n(2n+1)}{2}\frac{n(n+1)}{2}-2n\frac{n(n^2+3n+2)}{6}=\frac23 n^4 + \frac12 n^3 - \frac16 n^2.$$

Pero esta no es la complejidad temporal del bucle. Es el valor de la triple suma en forma cerrada.

Answer 2

Según Wolfram Alpha , $$ \sum_{i=1}^{2n} \sum_{j=1}^{n} \sum_{k=j}^{n} i-j = \frac23 n^4 + \frac12 n^3 - \frac16 n^2. $$

Pero ese no es el complejidad temporal del bucle. En cambio, es el valor de la variable $r$ al final del bucle.

Para obtener la complejidad temporal, ignora los valores que se suman o restan a $r$ dentro del bucle. Sólo quieres la clase big-O del número total de operaciones realizadas.

Un sencillo truco para contar las operaciones es sustituir $i - j$ con $1.$ Esto subestimará las operaciones, pero no por más de algún factor constante, y big-O significa que no tienes que preocuparte por el factor constante.

Answer 3

$$\sum_{i=1}^{2n} \sum_{j=1}^{n} \sum_{k=j}^{n} i-j = \sum\limits_{i=1}^{2n} \sum\limits_{j=1}^n (i-j) \cdot (n-j+1) = \sum\limits_{i=1}^{2n} in^2 -\frac{in(n+1)}{2} + in - \frac{n^2(n+1)}{2} + \frac{n(n+1)(2n+1)}{6} - \frac{n(n+1)}{2} = \frac{2n^3(2n+1)}{2} - \frac{2n^2(n+1)(2n+1)}{4} + \frac{2n^2(2n+1)}{2} - \frac{2n^3(n+1)}{2} + \frac{2n^2(n+1)(2n+1)}{6} - \frac{2n^2(n+1)}{2} = \frac{2}{3}n^4 + \frac{n^3}{2} - \frac{n^2}{6} $$

Answer 4

$$\begin{align} \sum_{i=1}^{2n}\sum_{j=1}^n\sum_{k=1}^ni-j &=\sum_{i=1}^{2n}\sum_{k=1}^n\sum_{j=1}^ki-j\\ &=\sum_{k=1}^n\sum_{j=1}^k\sum_{i=1}^{2n}i-\sum_{i=1}^{2n}\sum_{i=1}^n\sum_{j=1}^kj\\ &=\sum_{k=1}^n k\binom {2n+1}2-2n\sum_{k=1}^n\binom {k+1}2\\ &=\binom {n+1}2\binom {2n+1}2-2n\binom {n+2}3\\ &=2n\binom {n+1}2\left[\frac {2n+1}2-\frac {n+2}3\right]\\ &=2n\binom {n+1}2\frac {4n-1}6\\ &=\frac 13 n(4n-1)\frac {(n+1)n}2\\ &=\frac 16n^2(n+1)(4n-1)\quad \equiv \frac 23 n^4+\frac 12 n^3-\frac 16 n^2\\ \end{align}$$