Notación Big O

¿Qué es la notación Big O?

La notación Big O es una notación matemática usada para describir el rendimiento o la complejidad de un algoritmo. En particular, describe el peor caso y nos ayuda a entender cómo crecen el tiempo de ejecución o los requisitos de memoria a medida que aumenta el tamaño de la entrada.

Big O nos da una comprensión de alto nivel de la complejidad temporal o espacial de un algoritmo, permitiéndonos comparar enfoques y elegir el más eficiente.

Complejidades temporales comunes

Estas son las complejidades Big O más comunes, de mejor a peor:

// Example: Array access by index
function getFirstElement(arr) {
  return arr[0]; // Always takes the same time
}

// Example: Hash table lookup
const map = new Map([['key', 'value']]);
map.get('key'); // O(1) lookup

// Example: Binary search
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  
  return -1;
}

// With each iteration, we cut the search space in half
// For 1000 items, only ~10 comparisons needed!

// Example: Finding max in unsorted array
function findMax(arr) {
  let max = arr[0];
  
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] > max) {
      max = arr[i];
    }
  }
  
  return max;
}

// Must check every element once

// Example: Merge Sort
function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  
  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  
  return result.concat(left.slice(i)).concat(right.slice(j));
}

// Example: Bubble Sort
function bubbleSort(arr) {
  const n = arr.length;
  
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  
  return arr;
}

// For 1000 items, this makes ~1,000,000 comparisons!

// Example: Naive Fibonacci (inefficient)
function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

// Exponential growth - fibonacci(50) would take years!
// This is why we need dynamic programming

Tabla de complejidad Big O

Complejidad espacial

Big O también describe la complejidad de espacio (memoria). Mide cuánta memoria adicional necesita un algoritmo.

// Uses fixed amount of space
function sum(a, b) {
  return a + b; // No extra space
}

// Creates new array
function double(arr) {
  const result = [];
  for (let i = 0; i < arr.length; i++) {
    result.push(arr[i] * 2);
  }
  return result;
}

Big O, Big Omega y Big Theta

Reglas para calcular Big O

// This is O(n), not O(2n)
function example(arr) {
  for (let i = 0; i < arr.length; i++) { } // O(n)
  for (let i = 0; i < arr.length; i++) { } // O(n)
  // Total: O(n + n) = O(2n) = O(n)
}

// This is O(n²), not O(n² + n)
function example(arr) {
  for (let i = 0; i < arr.length; i++) { } // O(n)
  
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) { } // O(n²)
  }
  // Total: O(n + n²) = O(n²)
}

// This is O(a + b), not O(n)
function example(arr1, arr2) {
  for (let i = 0; i < arr1.length; i++) { } // O(a)
  for (let i = 0; i < arr2.length; i++) { } // O(b)
  // Total: O(a + b)
}