AALIE

Tabla de Sumatorias Comunes

Fórmulas de sumatorias y propiedades de transformación usadas para cerrar costos iterativos y recurrencias.

9. Tabla de Sumatorias Comunes

En el análisis de algoritmos, las sumatorias aparecen constantemente al contar cuántas veces se ejecuta un bloque de código. Saber resolverlas —o al menos reconocerlas— es tan importante como saber calcular límites.

Esta sección reúne las sumatorias más comunes organizadas en tres niveles de complejidad: simples (un solo índice), dobles (dos índices anidados) y triples (tres índices anidados). Para cada una se muestra la notación de suma, su forma cerrada y un ejemplo de en qué tipo de código aparece.

Convención

En este documento se usan las siguientes notaciones: $n$ es el tamaño de la entrada, $i, j, k$ son los índices de suma, y las fórmulas cerradas son exactas salvo que se indique lo contrario.

¿Por qué importan las sumatorias en algoritmos?

For simple $(i = 1 to n)$ : genera una sumatoria simple de la forma $\sum_{i = 1}^{n} f (i)$ .
For anidado con límite variable $(j = 1 to i)$ : genera una sumatoria doble. El cuerpo se ejecuta $\sum_{i = 1}^{n} \sum_{j = 1}^{i} 1$ veces.
Triple anidado: genera una sumatoria triple. Aparecen en algoritmos de multiplicación de matrices o recorridos de tensores.

Regla de oro

Para resolver una sumatoria doble o triple, se resuelve de adentro hacia afuera, convirtiendo cada sumatoria interna en su forma cerrada antes de continuar con la externa.

9.1 Sumatorias Simples

Una sumatoria simple tiene un solo índice que recorre un rango. Aparecen cuando hay un único ciclo cuyo cuerpo ejecuta una función de ese índice.

9.1.1 Sumatorias básicas de constantes y potencias

Sumatorias básicas de constantes y potencias

Sumatoria	Forma cerrada	Orden	Dónde aparece en código
Suma de 1's (constante)	$\sum_{i = 1}^{n} 1 = n$	$Θ (n)$	`for i <- 1 to n do op_constante endfor`
Suma de i (aritmética)	$\sum_{i = 1}^{n} i = \frac{n ( n + 1 )}{2}$	$Θ (n^{2})$	`for i <- 1 to n do for j <- 1 to i do op endfor endfor`
Suma de i² (cuadrática)	$\sum_{i = 1}^{n} i^{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6}$	$Θ (n^{3})$	`for j <- 1 to i do for k <- 1 to j do op endfor`
Suma de i³ (cúbica)	$\sum_{i = 1}^{n} i^{3} = [\frac{n ( n + 1 )}{2}]^{2}$	$Θ (n^{4})$	Anidamiento de tres ciclos con límites variables
Suma de i^k (potencia k)	$\sum_{i = 1}^{n} i^{k} \sim \frac{n ^{k + 1}}{k + 1}$	$Θ (n^{k + 1})$	Ciclo con cuerpo de costo polinomial

9.1.2 Sumatorias geométricas y exponenciales

Sumatorias geométricas y exponenciales

Sumatoria	Forma cerrada	Orden	Dónde aparece en código
Geométrica (r != 1)	$\sum_{i = 0}^{n} r^{i} = \frac{r ^{n + 1} - 1}{r - 1}$	$Θ (r^{n}) si r > 1$	Árbol binario completo: número total de nodos
Geométrica decreciente (0 < r < 1)	$\sum_{i = 0}^{\infty} r^{i} = \frac{1}{1 - r}$	$Θ (1)$ (constante)	Convergencia de serie infinita
Potencias de 2 (suma)	$\sum_{i = 0}^{n} 2^{i} = 2^{n + 1} - 1$	$Θ (2^{n})$	Torres de Hanoi, Fibonacci recursivo
Potencias de 2 (suma parcial)	$\sum_{i = 0}^{l g n} 2^{i} = 2 n - 1$	$Θ (n)$	Árbol binario de altura log(n)
Suma de a^i (a entero > 1)	$\sum_{i = 0}^{n} a^{i} = \frac{a ^{n + 1} - 1}{a - 1}$	$Θ (a^{n})$	Recursión de tipo aT(n-1) + c

9.1.3 Sumatorias logarítmicas y armónicas

Sumatorias logarítmicas y armónicas

Sumatoria	Forma cerrada / Aproximación	Orden	Dónde aparece
Armónica H(n)	$\sum_{i = 1}^{n} \frac{1}{i} = H (n) \sim ln (n) + 0.5772$	$Θ (lo g n)$	Quicksort caso promedio, búsqueda en hashing
Suma de log(i)	$\sum_{i = 1}^{n} lo g (i) = lo g (n!) \sim n lo g (n)$	$Θ (n lo g n)$	Merge Sort, Heap Sort: costo total de comparaciones
Suma de i*log(i)	$\sum_{i = 1}^{n} i lo g (i) \sim \frac{n ^{2} l o g n}{2}$	$Θ (n^{2} lo g n)$	Algoritmos de ordenamiento anidados
Suma de 1/i² (convergente)	$\sum_{i = 1}^{\infty} \frac{1}{i ^{2}} = \frac{π ^{2}}{6} \sim 1.6449$	$Θ (1)$ (constante)	Análisis de probabilidades en hashing
Suma de log(i)^2	$\sum_{i = 1}^{n} (lo g i)^{2} \sim n (lo g n)^{2}$	$Θ (n lo g^{2} n)$	Algoritmos con subproblemas logarítmicos

Nota

La serie armónica $H (n) = 1 + \frac{1}{2} + \frac{1}{3} + \dots + \frac{1}{n}$ es fundamental en el análisis del caso promedio de Quicksort y aparece frecuentemente cuando hay ciclos cuyo número de iteraciones depende de un valor que decrece de forma no uniforme.

9.2 Sumatorias Dobles

Una sumatoria doble tiene dos índices anidados. Aparece cuando hay dos ciclos anidados, donde el límite del ciclo interno puede depender del externo.

Cómo resolverlas

Primero se resuelve la sumatoria interna, obteniendo una función de $i$ , y luego esa función se usa como término de la sumatoria externa.

9.2.1 Dobles con límites fijos

Ambos índices van de 1 a n (límites independientes entre sí).

Sumatorias dobles con límites fijos

Sumatoria doble	Forma cerrada	Orden	Tipo de código
$\sum_{i = 1}^{n} \sum_{j = 1}^{n} 1$	$n \cdot n = n^{2}$	$Θ (n^{2})$	`for i <- 1 to n do for j <- 1 to n do op_constante`
$\sum_{i = 1}^{n} \sum_{j = 1}^{n} i$	$n \cdot \frac{n ( n + 1 )}{2} = \frac{n ^{2} ( n + 1 )}{2}$	$Θ (n^{3})$	`for i <- 1 to n do for j <- 1 to n do op que cuesta i`
$\sum_{i = 1}^{n} \sum_{j = 1}^{n} j$	$n \cdot \frac{n ( n + 1 )}{2} = \frac{n ^{2} ( n + 1 )}{2}$	$Θ (n^{3})$	`for i <- 1 to n do for j <- 1 to n do op que cuesta j`
$\sum_{i = 1}^{n} \sum_{j = 1}^{n} i \cdot j$	$[\frac{n ( n + 1 )}{2}]^{2}$	$Θ (n^{4})$	Cuerpo con costo proporcional a i*j
$\sum_{i = 1}^{n} \sum_{j = 1}^{n} c$ (c constante)	$c \cdot n^{2}$	$Θ (n^{2})$	Dos ciclos anidados con cuerpo de costo c

9.2.2 Dobles con límite variable (el más común en clase)

El límite del ciclo interno depende del índice externo. Son las más frecuentes al analizar algoritmos de ordenamiento.

Sumatorias dobles con límite variable

Sumatoria doble	Desarrollo	Forma cerrada	Orden
$\sum_{i = 1}^{n} \sum_{j = 1}^{i} 1$	$= \sum_{i = 1}^{n} i$	$\frac{n ( n + 1 )}{2}$	$Θ (n^{2})$
$\sum_{i = 1}^{n} \sum_{j = 1}^{i} j$	$= \sum_{i = 1}^{n} \frac{i ( i + 1 )}{2}$	$\frac{n ( n + 1 ) ( n + 2 )}{6}$	$Θ (n^{3})$
$\sum_{i = 1}^{n} \sum_{j = i}^{n} 1$	$= \sum_{i = 1}^{n} (n - i + 1)$	$\frac{n ( n + 1 )}{2}$	$Θ (n^{2})$
$\sum_{i = 1}^{n} \sum_{j = 1}^{n - i} 1$	$= \sum_{i = 1}^{n} (n - i)$	$\frac{n ( n - 1 )}{2}$	$Θ (n^{2})$
$\sum_{i = 1}^{n} \sum_{j = 1}^{i} i$	$= \sum_{i = 1}^{n} i^{2}$	$\frac{n ( n + 1 ) ( 2 n + 1 )}{6}$	$Θ (n^{3})$
$\sum_{i = 1}^{n} \sum_{j = i}^{n} (j - i)$	$= \sum_{i = 1}^{n} \frac{( n - i ) ( n - i + 1 )}{2}$	$\sim \frac{n ^{3}}{6}$	$Θ (n^{3})$

Ejemplo de clase

La sumatoria $\sum_{i = 1}^{n} (i + 1)$ aparece al contar el encabezado del for interno en el ejemplo de AlgoritmoSM2 con límite variable.

i = 1 \sum n (i + 1) = i = 1 \sum n i + i = 1 \sum n 1 = \frac{n ( n + 1 )}{2} + n = \frac{n ^{2} + 3 n}{2}

9.2.3 Dobles con ciclos de tipo logarítmico

Cuando uno de los ciclos usa multiplicación en vez de incremento, por ejemplo j <- j*2, el límite de iteraciones es logarítmico.

Sumatorias dobles con ciclos de tipo logarítmico

Sumatoria doble	Forma cerrada	Orden	Tipo de código
$\sum_{i = 1}^{n} \sum_{j = 1}^{l o g n} 1$	$n lo g (n)$	$Θ (n lo g n)$	`for i <- 1 to n do j <- 1 while j <= n: j <- j*2`
$\sum_{i = 1}^{n} \sum_{j = i}^{n, j * = 2} 1$	$\sum_{i = 1}^{n} lo g (n / i) \sim n lo g (n) - n$	$Θ (n lo g n)$	Ciclo externo lineal, interno geométrico
$\sum_{i = 1}^{l o g n} \sum_{j = 1}^{n} 1$	$n lo g (n)$	$Θ (n lo g n)$	`for i <- 1 to log n do for j <- 1 to n do op`
$\sum_{i = 1}^{l o g n} \sum_{j = 1}^{i} 1$	$\frac{l o g ( n ) ( l o g ( n ) + 1 )}{2} \sim \frac{( l o g n ) ^{2}}{2}$	$Θ (lo g^{2} n)$	Doble ciclo con ambos límites log

9.3 Propiedades útiles para manipular sumatorias

Estas propiedades permiten descomponer o simplificar sumatorias complejas antes de resolverlas.

Propiedades útiles para manipular sumatorias

Propiedad	Fórmula	Para qué sirve
Linealidad (constante)	$\sum c \cdot f (i) = c \sum f (i)$	Sacar constantes fuera de la sumatoria
Linealidad (suma)	$\sum [f (i) + g (i)] = \sum f (i) + \sum g (i)$	Separar términos de una sumatoria compleja
Cambio de índice	$\sum_{i = 1}^{n} f (i) = \sum_{i = 0}^{n - 1} f (i + 1)$	Reindexar para aplicar fórmulas conocidas
Telescópica	$\sum_{i = 1}^{n} [f (i) - f (i - 1)] = f (n) - f (0)$	Cancelar términos consecutivos
Separación de términos	$\sum_{i = 1}^{n} = \sum_{i = 1}^{m} + \sum_{i = m + 1}^{n}$	Dividir la suma en partes convenientes
Inversión de orden	$\sum_{i = 1}^{n} f (i) = \sum_{i = 1}^{n} f (n + 1 - i)$	Invertir el orden de suma (útil en pares)
Sumatoria de sumatoria	$\sum_{i = 1}^{n} \sum_{j = 1}^{i} 1 = \sum_{i = 1}^{n} i = \frac{n ( n + 1 )}{2}$	Colapsar doble a simple
Truco de la suma doble	$2 \sum_{i = 1}^{n} f (i) = suma directa + suma invertida$	Sumar la sumatoria con su copia invertida para cancelar términos