Notación Big-O

La notación Big-O describe cómo crece el coste de un algoritmo (en tiempo o memoria) a medida que aumenta el tamaño de la entrada n. Ignora constantes y términos menores para centrarse en el comportamiento a gran escala.

Complejidades habituales (de mejor a peor)

Notación	Nombre	Ejemplo
`O(1)`	Constante	Acceder a `arr[0]`
`O(log n)`	Logarítmica	Búsqueda binaria
`O(n)`	Lineal	Recorrer un array
`O(n log n)`	Linearítmica	Merge sort, quick sort
`O(n²)`	Cuadrática	Bubble sort, bucles anidados
`O(2ⁿ)`	Exponencial	Fibonacci recursivo ingenuo

Ejemplos

// O(1): no depende del tamaño
function primero(arr) {
  return arr[0];
}

// O(n): una pasada por el array
function suma(arr) {
  let total = 0;
  for (const x of arr) total += x;
  return total;
}

// O(n²): un bucle dentro de otro
function pares(arr) {
  const salida = [];
  for (const a of arr) {
    for (const b of arr) {
      salida.push([a, b]);
    }
  }
  return salida;
}

La regla práctica: cuenta los bucles anidados sobre la entrada. Dos bucles anidados sobre n suelen ser O(n²).

Ejemplos

Comparar número de operaciones

function operacionesLineal(n) {
  let ops = 0;
  for (let i = 0; i < n; i++) ops++;
  return ops;
}
function operacionesCuadratico(n) {
  let ops = 0;
  for (let i = 0; i < n; i++)
    for (let j = 0; j < n; j++) ops++;
  return ops;
}
console.log("Lineal n=10:", operacionesLineal(10));
console.log("Cuadrático n=10:", operacionesCuadratico(10));