Al escribir código, no solo queremos que funcione, sino que funcione de manera eficiente. Pero, ¿cómo medimos la "eficiencia"? Podríamos usar un cronómetro para ver cuánto tarda un programa, pero ese método tiene problemas. El resultado cambiaría dependiendo de la velocidad del ordenador, del lenguaje de programación o incluso de los datos de entrada específicos.

Necesitamos una forma de analizar algoritmos que sea independiente del hardware y de los detalles de implementación. Aquí es donde entra el análisis asintótico. En lugar de medir el tiempo en segundos, contamos el número de operaciones que realiza un algoritmo en función del tamaño de su entrada, que llamamos $n$.

Nos centramos en cómo se comporta el tiempo de ejecución a medida que $n$ se hace muy, muy grande. Este comportamiento asintótico nos da una visión de alto nivel sobre la escalabilidad de un algoritmo. ¿Se ralentiza drásticamente a medida que los datos crecen, o se mantiene rápido y eficiente? La notación asintótica nos proporciona el lenguaje matemático para responder a esta pregunta.

La notación más común en el análisis de algoritmos es la Big O (Gran O). Describe el límite superior del tiempo de ejecución de un algoritmo. En otras palabras, Big O establece una garantía: el rendimiento de tu algoritmo no será peor que una determinada tasa de crecimiento.

Puedes pensar en ello como el peor escenario posible. Si un algoritmo tiene una complejidad de $O(n^2)$, significa que, en el peor de los casos, el número de operaciones crecerá de forma cuadrática con respecto al tamaño de la entrada.

Mientras que Big O nos da el peor escenario, a veces es útil conocer el mejor escenario. Para esto, usamos la notación Big Omega ($\\Omega$). Big Omega establece un límite inferior para el tiempo de ejecución de un algoritmo. Garantiza que el rendimiento no será mejor que una cierta tasa de crecimiento.

Cuando un algoritmo tiene el mismo límite superior e inferior, decimos que tiene un límite ajustado. Usamos la notación Big Theta ($\\Theta$) para esto. Si un algoritmo es $\\Theta(g(n))$, significa que su tiempo de ejecución crece a la misma tasa que $g(n)$, tanto en el mejor como en el peor de los casos (ignorando factores constantes).

En esencia, $f(n) \in \Theta(g(n))$ es una afirmación más precisa que $f(n) \in O(g(n))$, ya que nos dice que el crecimiento del algoritmo está "atrapado" entre dos múltiplos de $g(n)$.

La notación asintótica sigue algunas propiedades matemáticas útiles que simplifican el análisis. Dos de las más importantes son la transitividad y la suma.

Transitividad: Si una función $f(n)$ está limitada por $g(n)$, y $g(n)$ está limitada por $h(n)$, entonces $f(n)$ también está limitada por $h(n)$. Esto se aplica a $O$, $\Omega$ y $\Theta$.

Regla de la suma: Al analizar dos partes de un algoritmo que se ejecutan en secuencia, la complejidad total está determinada por la parte que tiene la tasa de crecimiento más lenta (la más grande). Simplemente nos quedamos con el término dominante.

Por ejemplo, si un algoritmo primero realiza una operación que tarda $O(n)$ y luego otra que tarda $O(n^2)$, la complejidad total del algoritmo es $O(n^2)$. La parte $O(n)$ se vuelve insignificante a medida que $n$ crece.

Estas definiciones y propiedades forman la base matemática para analizar y comparar la eficiencia de los algoritmos de una manera rigurosa y estandarizada.