Complejidad algoritmica

Que es la complejidad algoritmica y como usar Big-O para analizar el tiempo y la memoria de un algoritmo.

La complejidad algoritmica mide como crece el consumo de recursos de un algoritmo (tiempo de ejecucion y memoria) a medida que aumenta el tamano de la entrada, que solemos llamar n. No nos dice cuantos segundos tarda un programa en una maquina concreta, sino como se comporta cuando los datos crecen: si duplicar la entrada duplica el trabajo, lo cuadruplica o lo dispara sin control.

Entender esto es clave porque te permite comparar dos soluciones sin depender del hardware, del lenguaje ni de micro-optimizaciones, y anticipar si un algoritmo seguira siendo viable con un millon de elementos. Es uno de los temas mas preguntados en entrevistas tecnicas.

Que medimos: operaciones, no segundos

El tiempo de reloj depende de la CPU, del lenguaje, de la carga del sistema y hasta del compilador. Por eso, en lugar de medir segundos, contamos operaciones basicas (comparaciones, asignaciones, accesos) en funcion de n. Lo que nos interesa es la tasa de crecimiento: como escala ese conteo cuando n se vuelve grande.

Por ejemplo, recorrer una lista de n elementos hace del orden de n operaciones. Que cada iteracion cueste 3 o 5 instrucciones internas no cambia la idea central: el trabajo crece de forma proporcional a n.

Notacion Big-O

Big-O describe la cota superior asintotica de un algoritmo: cuanto crece su costo en el peor caso cuando n tiende a infinito. Escribimos O(n), O(n^2), O(log n), etc. Para obtener el Big-O de un algoritmo se aplican dos reglas practicas:

• Se ignoran las constantes: O(2n) se simplifica a O(n), y O(n / 2) tambien es O(n). Las constantes no cambian la forma de la curva.
• Se conserva solo el termino dominante: O(n^2 + n + 100) se simplifica a O(n^2), porque para n grande el termino cuadratico domina a todos los demas.

Grafico de tasas de crecimiento

Este grafico compara como escalan las complejidades mas comunes. Mientras mas empinada es la curva, peor escala el algoritmo cuando crece la entrada n.

La siguiente tabla vuelve tangible esa diferencia: muestra el numero aproximado de operaciones para distintos tamanos de entrada.

Complejidad temporal (tiempo)

La complejidad temporal describe como crece el numero de operaciones en funcion de n. Estas son las clases mas comunes, de la mejor a la peor.

O(1) — Constante

El costo no depende del tamano de la entrada: siempre hace la misma cantidad de trabajo. Acceder a un indice de un array o leer una clave de un objeto o Map es O(1).

function firstElement(items) {
  return items[0];
}

O(log n) — Logaritmica

En cada paso se descarta la mitad de los datos, asi que el numero de pasos crece muy lentamente. El ejemplo clasico es la busqueda binaria sobre un array ordenado.

function binarySearch(sortedItems, target) {
  let low = 0;
  let high = sortedItems.length - 1;

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    if (sortedItems[mid] === target) return mid;
    if (sortedItems[mid] < target) low = mid + 1;
    else high = mid - 1;
  }

  return -1;
}

O(n) — Lineal

El trabajo crece de forma proporcional a n: un solo recorrido de la entrada. Buscar el maximo de una lista es O(n).

function findMax(numbers) {
  let max = numbers[0];
  for (const value of numbers) {
    if (value > max) max = value;
  }
  return max;
}

O(n log n) — Linealitmica

Es el mejor costo posible para ordenar por comparaciones. Algoritmos como merge sort o el sort nativo del lenguaje son O(n log n): hacen log n niveles de division y n trabajo en cada nivel.

function sortAscending(numbers) {
  return [...numbers].sort((a, b) => a - b);
}

O(n^2) — Cuadratica

Aparece con bucles anidados que recorren la entrada dentro de otro recorrido de la entrada. Comparar cada elemento con todos los demas para buscar duplicados de forma ingenua es O(n^2).

function hasDuplicate(items) {
  for (let i = 0; i < items.length; i++) {
    for (let j = i + 1; j < items.length; j++) {
      if (items[i] === items[j]) return true;
    }
  }
  return false;
}

O(2^n) — Exponencial

El costo se duplica con cada elemento adicional. La version recursiva ingenua de Fibonacci recalcula los mismos valores una y otra vez, generando un arbol de llamadas que crece exponencialmente. Es inviable incluso para entradas moderadas.

function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

Complejidad espacial (memoria)

La complejidad espacial mide cuanta memoria adicional necesita un algoritmo mas alla de la entrada. Se suele reportar el espacio auxiliar: las estructuras nuevas que creas, mas la memoria del stack por la recursion. La entrada en si no siempre se cuenta.

O(1) espacio

El algoritmo usa una cantidad fija de memoria extra sin importar el tamano de la entrada, tipicamente unas pocas variables.

function sum(numbers) {
  let total = 0;
  for (const value of numbers) {
    total += value;
  }
  return total;
}

O(n) espacio

La memoria extra crece con la entrada, por ejemplo al construir una nueva estructura del tamano de n.

function double(numbers) {
  const result = [];
  for (const value of numbers) {
    result.push(value * 2);
  }
  return result;
}

La recursion tambien cuesta memoria

Cada llamada recursiva pendiente ocupa un marco en el call stack. Una recursion lineal como la siguiente usa O(n) de memoria en el stack, aunque no cree ninguna estructura de datos explicita.

function sumTo(n) {
  if (n === 0) return 0;
  return n + sumTo(n - 1);
}

Mejor, peor y caso promedio

Un mismo algoritmo puede comportarse distinto segun la entrada concreta. Tomemos una busqueda lineal:

• Mejor caso — el elemento buscado esta en la primera posicion: O(1).
• Peor caso — el elemento esta al final o no existe: O(n).
• Caso promedio — en promedio se recorre la mitad de la lista: O(n).

Cuando alguien dice “la complejidad de este algoritmo es O(n)” casi siempre se refiere al peor caso, porque es la garantia mas util: nos dice que tan mal puede ir como maximo.

Como analizar tu codigo

Algunas reglas practicas para estimar el Big-O de un fragmento de codigo:

• Bucle simple sobre la entrada: O(n).
• Bucles anidados sobre la entrada: se multiplican, dos niveles dan O(n^2).
• Dividir el problema a la mitad en cada paso: aparece un factor log n (como en la busqueda binaria).
• Operaciones consecutivas: se suman y luego se conserva el termino dominante (O(n) + O(n^2) es O(n^2)).
• Recursion: dibuja el arbol de llamadas; su tamano total es la complejidad temporal, y su profundidad, el costo de memoria en el stack.