# Complejidad
La complejidad de un algoritmo nos sirve para describir cómo crece el tiempo y la memoria de un algoritmo, conforme crece el tamaño de la entrada.

Nos importa porque nos va a decir el peor caso posible de nuestra propuesta de solución al problema. En programación competitiva, sabemos de antemano los límites de la entrada del problema, entonces el análisis de complejidad nos sirve para estimar si nuestra solución cumple con las restricciones de tiempo y memoria.

## Notación O mayúscula
Sean $f(n)$ y $g(n)$ dos funciones positivas. Entonces decimos que $f(n) = O(g(n))$ si $\displaystyle \lim_{n \to \infty} \dfrac{f(n)}{g(n)} = c$, donde $c$ es una constante finita. También decimos que $g(n)$ es asintóticamente similar a $f(n)$.

Ejemplo: sean $f(n)=2n^2+5n+8$ y $g(n)=n^2$. Entonces vemos que $\displaystyle \lim_{n \to \infty} \dfrac{f(n)}{g(n)} = 2$, lo que quiere decir que cuando la $n$ es suficientemente grande, $f(n) \approx 2g(n)$.


Ejemplo: sean $f(n)=3n^3+5n^2+7n+11$ y $g(n)=5n^2+11n$. Vemos que $\displaystyle \lim_{n \to \infty} \dfrac{f(n)}{g(n)} \to \infty$, por lo tanto, $g(n)$ no es asintóticamente similar a $f(n)$.


## ¿Para qué nos sirve esta notación?
Si $f(n) = O(g(n))$, donde $f(n)$ mide de forma precisa algún recurso del algoritmo (memoria o tiempo), usualmente queremos que $g(n)$ sea lo más simple posible, pues dicha función nos va a describir de forma simplificada el crecimiento de $f(n)$.

Ejemplo: si tenemos un algoritmo ficticio cuyo recurso del tiempo se puede modelar como $f(n)=2n^2+5n+8$, entonces es seguro decir que ese algoritmo "corre" en una complejidad $O(n^2)$.

## Propiedades de la notación O mayúscula
- $O(c \cdot g(n)) = O(g(n))$, es decir, las constantes no afectan la complejidad asintótica. Ejemplo: $O(2n^2) = O(n^2)$.
- $O(f(n) + g(n)) = \max(O(f(n)), O(g(n)))$, es decir, la función cuyo crecimiento asintótico sea mayor, es la que domina y la que se queda. Ejemplo: $O(2n^2+5n+8) = O(2n^2) = O(n^2)$.
- $O(a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1x + a_0) = O(x^n)$.
- $O(\log_a n) = O(\log_b n)$, es decir, la base del logaritmo no importa y simplemente escribimos $O(\log n)$. Esto se cumple, pues $\dfrac{\log_b n}{\log_a n} = \dfrac{\log n / \log b}{\log n / \log a} = \dfrac{\log a}{\log b}$, lo cual es una constante.

## Complejidades comunes
Las siguientes complejidades son comunes dentro del análisis de algoritmos, pues suelen aparecer muy frecuentemente. La siguiente lista está ordenada de menor a mayor:
- $O(1)$: constante (hallar el valor de una fórmula, imprimir algo en la consola, etc.)
- $O(\log n)$: logarítmica (búsqueda binaria, exponenciación binaria, etc.)
- $O(n)$: lineal (leer un arreglo elemento a elemento)
- $O(n \log n)$: linearítmica (ordenar un arreglo usando comparaciones, divide y vencerás, etc.)
- $O(n^2)$: cuadrática (ordenamiento por burbuja)
- $O(n^3)$: cúbica (floyd-warshall)
- ... todas las funciones polinómicas en orden creciente del grado ...
- $O(2^n)$: exponencial (muchos algoritmos de fuerza bruta)
- $O(3^n)$: exponencial
- ... todas las funciones exponenciales en orden creciente de la base ...
- $O(n!)$: factorial (enlistar todas las permutaciones de los primeros $n$ números)


## Operaciones elementales
Es la operación principal de interés de nuestro algoritmo, es la que vamos a medir con la función $f(n)$.

Ejemplo: para sumar todos los elementos de un arreglo de $n$ números, la operación de interés sería la suma, hay que ver cuántas veces se va a ejecutar. Entonces $f(n)$ es igual al número de veces que se ejecuta la suma.

Para convertir $f(n)$ a un tiempo en segundos, usualmente se usa la aproximación de que una computadora puede ejecutar $10^8$ operaciones elementales por segundo. Es decir, el tiempo en segundos es aproximadamente $\dfrac{f(n)}{10^8}$.

En la siguiente tabla podemos ver, para ciertos límites del tamaño del problema $n$, cuál es el algoritmo con la complejidad más grande que todavía entra en tiempo:

| $n$ | Peor algoritmo que entra en tiempo | Ejemplos |
| - | - | - |
| $\leq [10 .. 11]$ | $O(n!)$, $O(n^6)$ | Enlistar todas las permutaciones |
| $\leq [15 .. 18]$ | $O(2^n \cdot n^2)$ | Travelling salesman problem |
| $\leq [18 .. 22]$ | $O(2^n \cdot n)$ | DP's con máscara de bits |
| $\leq 100$ | $O(n^4)$ | DP en tres dimensiones donde cada estado cuesta $O(n)$ |
| $\leq 400$ | $O(n^3)$ | Floyd Warshall |
| $\leq 2000$ | $O(n^2 \log n)$ | Dos ciclos anidados y alguna estructura de datos dentro |
| $\leq 10^4$| $O(n^2)$ | Ordenamiento por burbuja, selección, inserción, ... |
| $\leq 10^6$ | $O(n \log n)$ | Merge sort, segment tree |
| $\leq 10^8$ | $O(n)$, $O(\log n)$, $O(1)$ | Leer datos de la entrada, búsqueda binaria, fórmula |