Big O Notation

Big O es la notación matemática que describe cómo escala un algoritmo: si duplicas el tamaño de los datos, ¿cuánto más tiempo tarda? O(1) significa constante: tarda lo mismo sin importar el tamaño. O(n) es lineal: el doble de datos significa el doble de tiempo. O(n²) es cuadrática: el doble de datos significa cuatro veces más tiempo.

Esta notación ignora constantes (O(2n) se simplifica a O(n)) porque lo que importa es la tendencia a gran escala.

Por qué importa Big O en la práctica: un algoritmo O(n²) funciona bien con 100 elementos (10.000 operaciones) pero es inutilizable con 1 millón (1 billón de operaciones). Un O(n log n) con 1 millón de elementos hace solo ~20 millones de operaciones. Los buscadores como Google indexan billones de páginas: si su búsqueda fuera O(n), tardaría horas.

En entrevistas técnicas de empresas como Google, Amazon o Meta, optimizar de O(n²) a O(n) es exactamente lo que buscan.

// O(1) - Constante: no depende del tamaño
function obtenerPrimero(array) {
  return array[0]; // Siempre igual de rápido
}

// O(n) - Lineal: crece proporcionalmente
function buscarLineal(array, objetivo) {
  for (let i = 0; i < array.length; i++) {
    if (array[i] === objetivo) return i; // Hasta n pasos
  }
  return -1;
}

// O(n²) - Cuadrática: bucle dentro de bucle
function burbuja(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j+1]) [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
    }
  }
  return arr;
}

// O(log n) - Logarítmica: divide a la mitad cada paso
function busquedaBinaria(arr, objetivo) {
  let izq = 0, der = arr.length - 1;
  while (izq <= der) {
    const mid = Math.floor((izq + der) / 2);
    if (arr[mid] === objetivo) return mid;
    arr[mid] < objetivo ? izq = mid + 1 : der = mid - 1;
  }
  return -1;
}

// O(n log n) - La mayoría de algoritmos de ordenamiento eficientes
// Merge Sort, Quick Sort, Heap Sort

// Orden de complejidad (mejor a peor):
// O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!)