Big O Notation (Complejidad)

O(1): Notación Constante El tiempo no depende del tamaño del input. Es decir, SIEMPRE se demorará el mismo tiempo.
O(n): Notación Lineal El tiempo aumenta de manera proporcional al tamaño del input. Es decir, demora más mientras más grande sea el input.
O(n2): Notación Cuadrática🚩 El incremento del tiempo es igual al cuadrado del tamaño del input. Es cuando dentro de la iteración de tu input haces otra iteración de tu input. (extra: si haces otra iteración dentro de la 2da iteración, pasa a ser O(n3), y así.)
O(log n): Notación Logarítmica El tiempo aumenta linealmente mientras que "n" sube exponencialmente. Por ejemplo, procesar un array de 10 elementos te tomará 1seg, uno de 100 elementos 2seg, uno de 100 elementos 3seg y así.
O(n log n) "Divide y conquistarás". Es cuando divides el input en partes para encontrar la solución a tu problema. El mejor ejemplo es merge sort. (Aquí un video para entender sobre merge sort https://www.youtube.com/watch?v=XaqR3G_NVoo)
O(2n): Notación Exponencial 🚩🚩 Cuando dentro de una función llamas + 1 vez a la misma función.
O(n!): Explosión Combinatoria🚩🚩🚩 Cuando para hallar la respuesta, necesitas hacer todas las combinaciones posibles. Ej: Cuál es la ruta más corta para pasar por X ciudades?

nicolezimerman/big-o-notation.md