Cómo calcular la Complejidad Temporal de un Algoritmo usando la Notación Big O

Tabla de contenidos

• 3 pasos para calcular la Complejidad Temporal
  • 1 – CONTAR las operaciones básicas en función del tamaño de la entrada
  • 2 – SUMAR la cantidad total de operaciones
  • 3 – SIMPLIFICAR la expresión
• Ejemplo A
• Ejemplo B
• Sumar y simplificar durante el paso 1
• Ejemplo C
• Ejemplo D

---

La complejidad temporal de un algoritmo es una medida teórica de la cantidad de tiempo que un algoritmo tarda en ejecutarse.

En este artículo nos centraremos en cómo calcularla mediante la notación Big O.

Si te interesa informarte sobre qué es la notación Big O y por qué es importante en el análisis de algoritmos, en este artículo del blog lo exploramos a fondo.

3 pasos para calcular la Complejidad Temporal

Podemos resumir el proceso a 3 simples pasos:

1. Contar las operaciones básicas en función del tamaño de la entrada (n)
2. Sumar la cantidad total de operaciones
3. Simplificar la expresión

Ahora analicemos cada paso con más detenimiento.

Sé que todo esto puede sonarte un tanto abstracto aún, así que, ¡veámoslo con ejemplos!

---

Ejemplo A

En este primer ejemplo analizaremos detalladamente cada paso.

Supongamos que tenemos una función que suma todos los elementos de un array:

function sumaArray(array) {  
   let suma = 0; // 1 operación básica
  
   for (let i = 0; i < array.length; i++) {
   // 1 operación básica para iniciar i
   // 1 operación básica para comparar i con array.length en cada iteración del bucle
   // 1 operación básica para incrementar i en cada iteración del bucle

      suma += array[i]; // 1 operación básica en cada iteración del bucle
   } 

   return suma; // 1 operación básica
}

Paso 1 : CONTAMOS las operaciones básicas en función del tamaño de la entrada

Siendo n la longitud del array de entrada, contamos las siguientes operaciones básicas:

1 (para la asignación inicial de la variable sum)
+ 1 (para iniciar i en el bucle for)
+ 1 * n = n (para comparar i con array.length en cada iteración del bucle)
+ 1 * n = n (para incrementar i en cada iteración del bucle)
+ 1 * n = n (para suma += array[i] en cada iteración del bucle)
+ 1 (para return suma).

En función de esto, podríamos expresar la complejidad temporal de este algoritmo así:

O(1) + O(1) + O(n) + O(n) + O(n) + O(1)

Paso 2: SUMAMOS la cantidad total de operaciones

Sumamos las operaciones básicas, agrupándolas según su orden de dependencia respecto a n:

O(1) + O(1) + O(n) + O(n) + O(n) + O(1) = O(3) + O(3n)

Paso 3: SIMPLIFICAMOS la expresión

1. Reducimos la expresión a su término de mayor orden:
   O(3) + O(3n) >> O(3n)
2. Descartamos la parte constante del término:
   O(3n) >> O(n)

Por lo tanto, la complejidad temporal de este algoritmo en notación Big O es O(n), llamada complejidad lineal, ya que el tiempo de ejecución crece linealmente con el tamaño de la entrada.

---

Ejemplo B

Ahora analicemos este algoritmo para encontrar el elemento máximo en un arreglo, viendo cada paso pero de forma más resumida:

function findMax(arr) {
  let max = -Infinity;  // O(1)
  for (let i = 0; i < arr.length; i++) {  // O(1) + (O(1)*n) + (O(1)*n)
    if (arr[i] > max) {  // O(1)*n
      max = arr[i];  // O(1)*n
    }
  }
  return max;  // O(1)
}

Paso 1 : CONTAMOS las operaciones básicas en función del tamaño de la entrada

Siendo n la longitud del array de entrada, contamos las siguientes operaciones básicas:

1 + 1 + (1*n) + (1*n) + (1*n) + (1*n) + 1

Entonces, podemos detallar el aporte de cada operación básica a la complejidad del algoritmo de la siguiente manera:

O(1) + O(1) + O(n) + O(n) + O(n) + O(n) + O(1)

Paso 2: SUMAMOS la cantidad total de operaciones

O(1) + O(1) + O(n) + O(n) + O(n) + O(n) + O(1) = O(3) + O(4n)

Paso 3: SIMPLIFICAMOS la expresión

O(3) + O(4n) = O(4n) = O(n)

Por lo tanto, la complejidad temporal de este algoritmo en notación Big O también es lineal o O(n).

---

Sumar y simplificar durante el paso 1

Ahora que estamos más familiarizados con los pasos básicos, para hacer el proceso más cómodo vamos a aplicar la suma (del paso 2) y la simplificación (del paso 3), durante el conteo del paso 1.

Tomemos el ejemplo anterior (tal cual lo comentamos antes):

function findMax(arr) {
  let max = -Infinity;  // O(1)
  for (let i = 0; i < arr.length; i++) {  // O(1) + (O(1)*n) + (O(1)*n)
    if (arr[i] > max) {  // O(1)*n
      max = arr[i];  // O(1)*n
    }
  }
  return max;  // O(1)
}

Y apliquemos la suma y la simplificación para indicar la cantidad de operaciones del bucle for:

function findMax(arr) {
  let max = -Infinity;  // O(1)
  for (let i = 0; i < arr.length; i++) {  // O(n)
    if (arr[i] > max) {  // O(1)
      max = arr[i];  // O(1)
    }
  }
  return max;  // O(1)
}

Entonces, podemos expresar el orden de operaciones requeridas de esta manera extendida:

O(1) + (O(n) * (O(1) + O(1))) + O(1)

Pero si sumamos y simplificamos la expresión que representa la cantidad de operaciones del bucle for, obtenemos una expresión más breve y fácil de leer:

O(1) + (O(n) * (O(1) + O(1))) + O(1)
= O(1) + (O(n) * O(2)) + O(1)
= O(1) + O(2n) + O(1)
= O(1) + O(n) + O(1)

Entonces, aplicamos el paso 2:

O(1) + O(n) + O(1) = O(2) + O(n)

Y por último aplicamos el paso 3:

O(2) + O(n) = O(n)

De esta forma llegamos a la misma conclusión que la vez anterior: la complejidad temporal de este algoritmo en notación Big O O(n) (complejidad lineal).

---

Ejemplo C

Ahora apliquemos todo lo que hemos discutido anteriormente para analizar la complejidad temporal de este algoritmo que calcula la suma de los elementos en una matriz 2D:

function sumMatrix(matrix) {
  let sum = 0;  // O(1)
  for (let i = 0; i < matrix.length; i++) {  // O(n)
    for (let j = 0; j < matrix[i].length; j++) {  // O(m)
      sum += matrix[i][j];  // O(1)
    }
  }
  return sum;  // O(1)
}

• Inicialización de sum: O(1)
• Bucle externo: O(n) (donde n es el número de filas)
• Bucle interno: O(m) (donde m es el número de columnas)
• Suma dentro del bucle interno: O(1)
• Return de sum: O(1)

Entonces, la complejidad total del algoritmo es:

O(1) + (O(n) * O(m) * O(1)) + O(1) =O(n * m)

La complejidad O(n * m) podría considerarse lineal respecto al número total de elementos de la matriz.

Aunque se describe mejor como «complejidad bidimensional» o simplemente O(n * m), para capturar el hecho de que la complejidad depende de dos parámetros diferentes: el número de filas (n) y el número de columnas (m) de la matriz.

---

Ejemplo D

Para finalizar, analicemos la complejidad temporal de este algoritmo de ordenamiento de burbuja (Bubble Sort):

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {  // O(n)
    for (let j = 0; j < arr.length - i - 1; j++) {  // O(n)
      if (arr[j] > arr[j + 1]) { // O(1)
        // Intercambiar arr[j] y arr[j + 1]
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];  // O(1)
      }
    }
  }
}

• Primer bucle for: O(n) (donde n es la longitud del arreglo)
• Segundo bucle for: O(n) (también en función de la longitud del arreglo)
• Comparación del if dentro del segundo bucle: O(1)
• Intercambio dentro del segundo bucle: O(1)

La complejidad total es:

O(n) * (O(n) * O(2)) = O(n) * O(2n) = O(2n²) = O(n²)

Es decir, este algoritmo tiene una complejidad temporal cuadrática (uno de los casos de la complejidad polinómica).

---

Escribí este artículo como resumen de lo que aprendí al estudiar este tema. Espero que te sea útil a ti también para entender mejor cómo utilizar la notación Big O para calcular la complejidad temporal de un algoritmo. 🤓

En un próximo artículo me centraré en desarrollar ejemplos prácticos de cómo calcular la complejidad espacial de los algoritmos mediante Big O.