BIG O - LA COMPLEJIDAD ALGORÍTMICA Y POR QUÉ LOS PROGRAMADORES DEBERÍAN ENTENDERLA

La complejidad algorítmica, más conocida como Big O, es uno de los conceptos fundamentales en informática y desarrollo de software. No se trata solo de una notación matemática aburrida: es la herramienta que te permite predecir cómo se comportará tu código cuando los datos crecen de verdad. Por ejemplo un programa que funciona perfectamente con 100 registros, pero cuando llega a un millón, se vuelve insoportablemente lento. Eso es exactamente lo que Big O ayuda a evitar.

¿Qué mide realmente Big O?

Big O es una notación matemática que describe el crecimiento del tiempo de ejecución o del consumo de memoria de un algoritmo en función del tamaño de la entrada, generalmente representado como n. No te dice el tiempo exacto en segundos, eso depende del hardware, sino cómo escala el costo a medida que n se hace más grande. Es la forma más efectiva de comparar algoritmos y tomar decisiones inteligentes sobre qué solución elegir.
Big O no dice si el código es bueno o malo. Muestra cómo se comportará el código cuando los datos crezcan. Un programador que entiende Big O deja de escribir código que “funciona” y empieza a escribir código que escala.
  • Mide la eficiencia de los algoritmos.
  • Depende del tamaño de los datos (n).
  • Predice el rendimiento a gran escala.

Ejemplos prácticos del día a día

  • Buscar un elemento en una lista sin ordenar: O(n) → Buscar uno por uno en el peor caso.
  • Búsqueda binaria (en una lista ordenada): O(log n) → Increíblemente más rápido.
  • Comparar todos los elementos con todos: O(n²) → Muy costoso.
  • Acceder directamente a una posición en un array: O(1) → Instantáneo.

¿Por qué Big O es importante?

Porque en sistemas reales los datos siempre crecen. Lo que funciona hoy con pocos usuarios o pocos registros puede colapsar en el futuro.
Entender Big O permite:
  • Optimizar el rendimiento del código.
  • Evitar cuellos de botella que solo aparecen en producción.
  • Escalar aplicaciones de forma eficiente.
  • Tomar decisiones técnicas fundamentadas.

Tipos de complejidad más comunes

Notación Nombre Comportamiento Ejemplo típico
O(1) Tiempo constante No importa cuántos datos haya, siempre tarda lo mismo Acceder a un elemento de un array por índice
O(log n) Logarítmica Crece muy lentamente. Muy eficiente Búsqueda binaria
O(n) Lineal Crece proporcionalmente al tamaño de los datos Recorrer una lista completa
O(n²) Cuadrática Crece muy rápido. Se vuelve problemático rápidamente Algoritmos de ordenamiento ingenuos

Ejemplos

  • O(1) — Tiempo constante: ¿Por qué es O(1)? No importa si el array tiene 10 o 10 millones de elementos, el acceso por índice es instantáneo.

    function obtenerElemento(array $array, int $indice): mixed
{
    return $array[$indice];   // Acceso directo por índice
}

// Uso
$usuarios = ['Ana', 'Luis', 'María', 'Carlos'];
echo obtenerElemento($usuarios, 2); // María → Siempre O(1)
  • O(n) — Complejidad lineal:¿Por qué es O(n)? En el peor caso se tiene que recorrer todos los elementos.

    function buscarLineal(array $array, mixed $buscado): ?int
{
    foreach ($array as $indice => $valor) {
   if ($valor === $buscado) {
  return $indice;
   }
    }
    return null;
}

// Uso
$frutas = ['manzana', 'plátano', 'cereza', 'melón'];
$resultado = buscarLineal($frutas, 'cereza');
echo $resultado !== null ? "Encontrado en posición: $resultado" : "No encontrado";
  • O(n²) — Complejidad cuadrática:¿Por qué es O(n²)? Dos bucles anidados → en el peor caso se realizan n × n comparaciones.

    function tieneDuplicados(array $array): bool
{
    $n = count($array);
    for ($i = 0; $i < $n; $i++) {
   for ($j = $i + 1; $j < $n; $j++) {
  if ($array[$i] === $array[$j]) {
      return true;
  }
   }
    }
    return false;
}
// Uso
$numeros = [1, 2, 3, 4, 5, 3];
echo tieneDuplicados($numeros) ? "Tiene duplicados" : "No tiene duplicados";
  • O(log n) — Búsqueda binaria (muy eficiente): ¿Por qué es O(log n)? Cada iteración reduce el espacio de búsqueda a la mitad. 

    function busquedaBinaria(array $array, mixed $buscado): ?int
{
    $inicio = 0;
    $fin = count($array) - 1;

    while ($inicio <= $fin) {
   $medio = (int) (($inicio + $fin) / 2);

   if ($array[$medio] === $buscado) {
  return $medio;
   }

   if ($array[$medio] < $buscado) {
  $inicio = $medio + 1;
   } else {
  $fin = $medio - 1;
   }
    }

    return null;
}

// Uso (el array DEBE estar ordenado)
$numeros = [1, 3, 5, 7, 9, 11, 13, 15, 17];
$resultado = busquedaBinaria($numeros, 13);
echo $resultado !== null ? "Encontrado en posición: $resultado" : "No encontrado";