GUÍA COMPLETA SOBRE NOTACIÓN BIG O EN ALGORITMOS

October 18, 2025

Introducción a la Notación Big O

La notación Big O es una herramienta fundamental en ciencias de la computación para describir la eficiencia de los algoritmos. Permite a los programadores evaluar y comparar el rendimiento de diferentes algoritmos en función del número de operaciones que realizan, especialmente cuando el tamaño de la entrada aumenta. En este tutorial, exploraremos en detalle qué es la notación Big O, cómo funciona, por qué es importante y cómo aplicarla en la práctica con ejemplos de código. Este conocimiento es esencial para cualquier desarrollador que busque optimizar sus programas y tomar decisiones informadas sobre qué algoritmos utilizar en un proyecto.

La notación Big O no mide el tiempo exacto de ejecución de un algoritmo, ya que este depende de factores como el hardware, el sistema operativo o el lenguaje de programación. En cambio, se centra en el crecimiento del número de operaciones en el peor caso posible, proporcionando una métrica estandarizada para comparar algoritmos. Por ejemplo, un algoritmo puede ser rápido con entradas pequeñas, pero su rendimiento puede degradarse significativamente con entradas grandes. Comprender esta métrica permite a los desarrolladores anticipar el comportamiento de su código en escenarios reales.

A lo largo de este tutorial, abordaremos los conceptos clave de la notación Big O, los tipos comunes de complejidad, y proporcionaremos ejemplos prácticos en Python para ilustrar cómo se aplica en algoritmos de búsqueda y ordenamiento. Al final, tendrás una comprensión sólida de cómo utilizar la notación Big O para mejorar la eficiencia de tus programas.

¿Qué es la Notación Big O?

La notación Big O describe el número de operaciones que un algoritmo realiza en función del tamaño de la entrada, denotado como n. Este enfoque matemático permite analizar el comportamiento de un algoritmo en el peor caso, es decir, el escenario en el que el algoritmo realiza el máximo número de operaciones posibles. Por ejemplo, si estás buscando un elemento en una lista desordenada, el peor caso ocurre cuando el elemento está al final de la lista o no existe, lo que requiere revisar cada elemento.

La notación Big O se expresa con un “O” seguido de una función que representa el crecimiento del número de operaciones. Por ejemplo, O(n) indica que el número de operaciones crece linealmente con el tamaño de la entrada, mientras que O(log n) sugiere un crecimiento logarítmico, mucho más eficiente para entradas grandes.

Consideremos un ejemplo práctico: supongamos que tienes una lista de nombres y necesitas encontrar a “Ana”. Un algoritmo de búsqueda lineal revisará cada elemento de la lista hasta encontrar a Ana o llegar al final. En el peor caso, este algoritmo realizará n operaciones, donde n es el número de elementos en la lista, lo que se representa como O(n).

def busqueda_lineal(lista, objetivo):
    for i in range(len(lista)):
        if lista[i] == objetivo:
            return i
    return -1

# Ejemplo de uso
nombres = ["Carlos", "Ana", "Beatriz", "David"]
resultado = busqueda_lineal(nombres, "Ana")
print(f"Índice de Ana: {resultado}")  # Salida: Índice de Ana: 1

En este código, la función busqueda_lineal tiene una complejidad de O(n) porque, en el peor caso, debe recorrer toda la lista.

Enfocándose en el Peor Caso

La notación Big O siempre se centra en el peor caso posible porque proporciona una garantía sobre el rendimiento máximo del algoritmo. Esto es crucial para aplicaciones donde la consistencia es importante, como sistemas en tiempo real o bases de datos masivas. Por ejemplo, imagina que eres un administrador de bases de datos buscando el registro de un estudiante en un sistema escolar. Si usas una búsqueda lineal, en el mejor caso podrías encontrar el registro inmediatamente (O(1)), pero en el peor caso tendrás que revisar todos los registros (O(n)).

Consideremos el ejemplo anterior. Si Ana está al principio de la lista, la búsqueda termina rápidamente. Sin embargo, la notación Big O no considera este caso óptimo, sino el escenario donde Ana está al final o no está en la lista. Esto asegura que los desarrolladores puedan planificar para el peor escenario posible y evitar sorpresas en el rendimiento.

Por ejemplo, si usamos una búsqueda binaria en una lista ordenada, la complejidad es O(log n), ya que el algoritmo divide el espacio de búsqueda a la mitad en cada iteración. Aquí está un ejemplo en Python:

def busqueda_binaria(lista, objetivo):
    izquierda, derecha = 0, len(lista) - 1
    while izquierda <= derecha:
        medio = (izquierda + derecha) // 2
        if lista[medio] == objetivo:
            return medio
        elif lista[medio] < objetivo:
            izquierda = medio + 1
        else:
            derecha = medio - 1
    return -1

# Ejemplo de uso
nombres_ordenados = ["Ana", "Beatriz", "Carlos", "David"]
resultado = busqueda_binaria(nombres_ordenados, "Ana")
print(f"Índice de Ana: {resultado}")  # Salida: Índice de Ana: 0

La búsqueda binaria es mucho más eficiente que la búsqueda lineal para listas grandes, ya que reduce exponencialmente el número de elementos a revisar.

Comparación de Tasas de Crecimiento

Uno de los aspectos más importantes de la notación Big O es que permite comparar cómo crecen los tiempos de ejecución de diferentes algoritmos a medida que aumenta el tamaño de la entrada. No todos los algoritmos crecen al mismo ritmo, y esta diferencia puede tener un impacto significativo en el rendimiento.

Por ejemplo, supongamos que cada operación en una base de datos toma 1 milisegundo. Para una lista de 10 elementos, una búsqueda lineal (O(n)) tomará 10 ms, mientras que una búsqueda binaria (O(log n)) tomará aproximadamente 3 ms, ya que log₂(10) ≈ 3. Ahora, si la lista crece a 1 mil millones de elementos, la búsqueda lineal tomará hasta 1 mil millones de milisegundos (aproximadamente 11 días), mientras que la búsqueda binaria tomará solo log₂(1,000,000,000) ≈ 30 ms.

Este contraste ilustra por qué la elección del algoritmo es crítica en aplicaciones con grandes volúmenes de datos, como motores de búsqueda o sistemas de recomendación. La notación Big O permite a los desarrolladores prever cómo se comportará un algoritmo bajo presión y elegir el más adecuado para su caso de uso.

Tipos Comunes de Complejidad Big O

Existen varios tipos de complejidad Big O que describen diferentes tasas de crecimiento. A continuación, se presentan los más comunes junto con ejemplos de algoritmos que los representan:

O(1) - Tiempo constante: El algoritmo realiza un número fijo de operaciones, independientemente del tamaño de la entrada. Un ejemplo es acceder a un elemento en un arreglo por su índice.

def obtener_elemento(arr, indice):
    return arr[indice]

# Ejemplo de uso
numeros = [1, 2, 3, 4, 5]
print(obtener_elemento(numeros, 2))  # Salida: 3

O(log n) - Tiempo logarítmico: El número de operaciones crece logarítmicamente, como en la búsqueda binaria. Este tipo de complejidad es ideal para grandes conjuntos de datos.
O(n) - Tiempo lineal: El número de operaciones crece proporcionalmente al tamaño de la entrada, como en la búsqueda lineal.
O(n log n) - Tiempo lineal-logarítmico: Común en algoritmos de ordenamiento eficientes como Quicksort o Mergesort.

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivote = arr[len(arr) // 2]
    izquierda = [x for x in arr if x < pivote]
    medio = [x for x in arr if x == pivote]
    derecha = [x for x in arr if x > pivote]
    return quicksort(izquierda) + medio + quicksort(derecha)

# Ejemplo de uso
numeros = [5, 2, 9, 1, 5, 6]
print(quicksort(numeros))  # Salida: [1, 2, 5, 5, 6, 9]

O(n²) - Tiempo cuadrático: Común en algoritmos de ordenamiento como la selección o la inserción, donde el número de operaciones crece con el cuadrado del tamaño de la entrada.

def ordenamiento_seleccion(arr):
    for i1 in range(len(arr)):
        min_idx = i1
        for i2 in range(i1 + 1, len(arr)):
            if arr[i2] < arr[min_idx]:
                min_idx = i2
        arr[i1], arr[min_idx] = arr[min_idx], arr[i1]
    return arr

# Ejemplo de uso
numeros = [5, 2, 9, 1, 5, 6]
print(ordenamiento_seleccion(numeros))  # Salida: [1, 2, 5, 5, 6, 9]

O(n!) - Tiempo factorial: Extremadamente ineficiente, común en problemas como el del viajante de comercio, donde el número de operaciones crece factorialmente.

Aplicaciones Prácticas de Big O

Comprender la notación Big O es crucial para optimizar el rendimiento de aplicaciones reales. Por ejemplo, en el desarrollo web, un algoritmo de búsqueda ineficiente puede ralentizar una página si la base de datos contiene millones de registros. En el desarrollo de videojuegos, un algoritmo de renderizado con complejidad O(n²) puede causar retrasos en pantallas con muchos objetos.

Un caso común es la optimización de consultas en bases de datos. Si usas una búsqueda lineal para encontrar un registro en una tabla no indexada, el tiempo de respuesta crecerá linealmente con el número de registros. Sin embargo, al indexar la tabla y usar una búsqueda binaria o una estructura de datos como un árbol B, puedes reducir la complejidad a O(log n), mejorando significativamente el rendimiento.

Otro ejemplo es en el procesamiento de datos masivos, como en la inteligencia artificial. Algoritmos de ordenamiento como Quicksort (O(n log n)) son preferidos sobre algoritmos como el ordenamiento por selección (O(n²)) para preparar conjuntos de datos grandes antes de entrenar un modelo.

Cómo Evaluar la Complejidad de un Algoritmo

Para determinar la complejidad Big O de un algoritmo, sigue estos pasos:

Identifica las operaciones básicas: Determina qué operaciones (como comparaciones, asignaciones o iteraciones) son las más significativas en el algoritmo.
Cuenta las operaciones en función de n: Analiza cómo cambia el número de operaciones cuando el tamaño de la entrada (n) aumenta.
Ignora constantes y términos no dominantes: En Big O, solo importa el término que crece más rápido. Por ejemplo, en O(3n² + 2n + 5), se simplifica a O(n²).
Considera el peor caso: Evalúa el algoritmo en el escenario donde realiza el máximo número de operaciones.

Por ejemplo, en el siguiente código de suma de elementos en una matriz, analizamos la complejidad:

def suma_matriz(matriz):
    total = 0
    for i in range(len(matriz)):
        for j in range(len(matriz[i])):
            total += matriz[i][j]
    return total

# Ejemplo de uso
matriz = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(suma_matriz(matriz))  # Salida: 45

Este algoritmo tiene dos bucles anidados, cada uno de tamaño n (si la matriz es n x n). Por lo tanto, la complejidad es O(n²), ya que realiza _n _ n* operaciones.

Limitaciones de la Notación Big O

Aunque la notación Big O es una herramienta poderosa, tiene limitaciones. No considera factores como la constante de tiempo de ejecución, que puede ser significativa en conjuntos de datos pequeños. Por ejemplo, un algoritmo O(n) con una constante alta puede ser más lento que un algoritmo O(n²) con una constante baja para entradas pequeñas.

Además, Big O no tiene en cuenta el uso de memoria (complejidad espacial), que puede ser crítico en sistemas con recursos limitados. Por ejemplo, un algoritmo de ordenamiento en el lugar (como Quicksort) usa menos memoria que uno que requiere estructuras adicionales (como Mergesort).

Finalmente, Big O se centra en el comportamiento asintótico, lo que significa que no siempre refleja el rendimiento en casos prácticos con entradas pequeñas o medianas. Por esta razón, es importante complementar el análisis Big O con pruebas de rendimiento reales.

Conclusiones

La notación Big O es una herramienta esencial para cualquier programador que desee escribir código eficiente y escalable. Al comprender cómo crece el número de operaciones en función del tamaño de la entrada, los desarrolladores pueden tomar decisiones informadas sobre qué algoritmos usar en diferentes contextos. Desde la búsqueda lineal (O(n)) hasta la búsqueda binaria (O(log n)) y algoritmos de ordenamiento como Quicksort (O(n log n)), la notación Big O proporciona una base sólida para comparar y optimizar algoritmos.

En este tutorial, hemos explorado los fundamentos de la notación Big O, sus aplicaciones prácticas y cómo analizar la complejidad de algoritmos con ejemplos en Python. Al aplicar estos conceptos, puedes mejorar el rendimiento de tus programas, especialmente en aplicaciones que manejan grandes volúmenes de datos. La clave está en entender las tasas de crecimiento y elegir algoritmos que equilibren eficiencia y claridad según las necesidades de tu proyecto.