Notación Big O: javascript

La notación Big O se utiliza para determinar cómo escala el trabajo que realiza un algoritmo a medida que crece el tamaño de los datos de entrada ( $n$ ).

Por ejemplo, el siguiente código tiene una complejidad temporal $O(1)$ :

const users = ["Ana", "Juan", "Pedro", "Lucía"];
const firstUser = users[0];

Esto significa que no importa qué tan grande sea el array de usuarios, acceder a users[0] siempre realizará la misma cantidad de trabajo.

La notación Big O no busca medir cuántos milisegundos tarda un algoritmo en ejecutarse, sino responder a esta pregunta: si paso de procesar 10 elementos a 10 millones de elementos, ¿cuánto más trabajo tendrá que hacer mi algoritmo?

---

1. $O(1)$ - Tiempo constante

El algoritmo realiza exactamente la misma cantidad de trabajo sin importar la cantidad de datos recibidos.

Da igual si el array de usuarios tiene 10 o 1.000.000 de elementos, el número de operaciones ejecutadas es fijo.

const users = ["Ana", "Juan", "Pedro", "Lucía"];
const firstUser = users[0];

---

2. $O(n)$ - Tiempo lineal

Imaginemos que queremos encontrar un usuario por su ID dentro de un array:

function findUser(users, id) {
  for (const user of users) {
    if (user.id === id) {
      return user;
    }
  }
}

En el peor de los casos (si el usuario está al final o no existe), tenemos que recorrer todo el array. Cuantos más elementos tengamos que procesar ( $n$ ), más pasos ejecutará la función. El crecimiento es lineal: a mayor cantidad de usuarios, proporcionalmente más trabajo realiza el algoritmo.

---

3. $O(n^2)$ - Tiempo cuadrático

Supongamos que queremos comparar cada usuario con todos los demás:

for (const userA of users) {
  for (const userB of users) {
    console.log(userA, userB);
  }
}

Esto representa un bucle anidado dentro de otro.

• Si tenemos 10 usuarios, console.log() se ejecutará 100 veces ( $10^2$ ).
• Si tenemos 100, se ejecutará 10.000 veces ( $100^2$ ).
• Para 1.000 usuarios un millón de veces

El costo escala cuadráticamente con respecto al tamaño de la entrada ( $n$ ).

---

4. $O(\log n)$ - Tiempo logarítmico

El tiempo logarítmico ocurre cuando la cantidad de pasos que requiere un algoritmo crece muy lentamente a medida que el tamaño de los datos ( $n$ ) aumenta.

Esto se debe a que, en cada paso, el algoritmo descarta una fracción constante de los datos

Supongamos que tenemos el siguiente array de números ordenados:

const numbers = [1, 4, 7, 12, 18, 25, 31, 40, 55];

Queremos encontrar el índice del número 31.

La manera directa sería recorrer los elementos uno por uno ( $O(n)$ ):

function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

Sin embargo, como el array ya está ordenado, podemos aplicar búsqueda binaria ( $O(\log n)$ ):

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const middle = Math.floor((left + right) / 2);

    if (arr[middle] === target) {
      return middle; // Retorna el índice donde se encuentra
    }

    if (arr[middle] < target) {
      left = middle + 1; // Descarta la mitad izquierda
    } else {
      right = middle - 1; // Descarta la mitad derecha
    }
  }

  return -1; // No se encontró el elemento
}

Paso a paso del algoritmo:

1. Primera iteración:

   • left = 0, right = 8.
   • El punto medio es middle = Math.floor((0 + 8) / 2) = 4 (numbers[4] es 18).
   • Como $18 < 31$ , descartamos toda la mitad izquierda ajustando left = 5.

2. Segunda iteración:

   • El rango activo ahora va del índice 5 al 8 ([25, 31, 40, 55]).
   • El punto medio es middle = Math.floor((5 + 8) / 2) = 6 (numbers[6] es 31).
   • Como arr[6] === 31, encontramos el objetivo en solo 2 pasos y retornamos el índice 6.

Al descartar la mitad del problema en cada ciclo, si duplicamos el tamaño del array solo agregamos un paso adicional al proceso. Por eso los algoritmos $O(\log n)$ crecen de forma sumamente lenta ante volúmenes masivos de datos

---

Resumen

Complejidad	Nombre	Ejemplo común
$O(1)$	Constante	Acceder a un elemento por su índice
$O(\log n)$	Logarítmico	Búsqueda binaria
$O(n)$	Lineal	Búsqueda simple / bucle for
$O(n^2)$	Cuadrático	Bucles anidados (for dentro de for)

Comments

[ygritte]

Amo los animales, cuento una breve historia del amor de mi vida acá🐾
Me encanta leer, La Montaña Mágica de Thomas Mann es mi libro preferido 📚
Mi película preferida es Groundhog Day, seguida muy de cerca por The Princess Bride
Disfruto mucho cocinar
Me gusta el xianxia, wuxia, y las novelas ligeras

@highflyer910 Ceann no earball?

[Thea]

Ceann!

Though picking Groundhog Day and The Princess Bride as top movies is already a solid green flag for this author:D