Notación "O Grandota" (Big O)

En ciencias de la computación es necesario conocer la eficiencia de un algoritmo y/o estructura de dato, para saber cuál nos conviene más usar pero, ¿cómo los clasificamos? ¿cómo sabemos que el algoritmo a usar no va a tomarle una enorme cantidad de pasos para darnos un resultado o va a consumir toda la memoria del equipo?

Es aquí donde entra la notación asintótica, que es la forma en la que podemos clasificar las complejidades de un algoritmo/estructura de dato ya sea en tiempo o en espacio; una de las más conocidas (pero es importante remarcar que no es la única) es la notación O grandota o Big O en el idioma anglosajón.

Ahora bien, ¿qué nos dice O grandota? Nos dice cuál va a ser el consumo más importante de recursos (ya sea de tiempo o espacio) dada una entrada de datos $\textbf{n}$ mediante una función y O grandota nos permite agrupar en clases dicho consumo, por lo que podemos decir que un algoritmo tiene (o está en) cierta complejidad y lo denotamos como $\textbf{O(f(n))}$. Formalmente lo definimos como sigue:

$$\text{“Sean f y g dos funciones } f: \mathbb{R^+} \longrightarrow \mathbb{R^+}, g: \mathbb{R^+} \longrightarrow \mathbb{R^+} \text{ decimos que } g(n)\in O(f(n))$$ $$\text{ si y solo si existen } c, n_0\in \mathbb{R^+} \text{ tales que } g(n) \leq cf(n), \forall n\geq n_0
\text{"}$$

Pero, ¿por qué el consumo más importante? Bueno, a los programadores siempre nos va a interesar el peor de los casos porque, si el algoritmo se comporta “bien” (o al menos de forma aceptable) en este caso, se comportará sustancialmente mejor en los demás. Por ende, O grandota nos es de mucha utilidad cuando querramos conocer qué tan mal se puede comportar un algoritmo. Algunas de las notaciones más comunes son las siguientes (conforme vamos descendiendo, la complejidad se considera peor):

Como este tipo de notación es de las más famosas, es importante destacar que también es de las más abusadas, por lo que hay que tener mucho cuidado al momento de utilizarla ¹ .