Durante mis años en la universidad nunca había escuchado sobre la notación Big-O, no es nada nuevo ni tampoco complejo de entender, es simplemente una notación para medir complejidad.

Para explicarlo, lo más fácil es mediante ejemplos

Expresiones Lineales:

Supongamos que tenemos una lista de 10 personas en un arreglo, y no estamos teniendo en cuenta el orden.

   const personas = ["Juan","Pedro", "Pablo", "Damian", "Maria","Diego", "Nelson", "Jose", "Monica","Juana"]

Si queremos encontrar a una persona de la lista, tendremos que iterar la lista y cuando encontremos a la persona, devolver un mensaje de Persona Encontrada, o en caso de que la persona no esté en la lista, comunicar Persona No encontrada.

Ejemplo de Código:

 function EncontrarPersona(nombre: string){
    for (let index = 0; index < personas.length; index++) {
        const persona = personas[index];

        if (persona === nombre)
            return "Persona Encontrada";
        }
        return "Persona No Encontrada";
    }

Como se puede ver, es una simple iteración, donde en el mejor de los casos, la persona se ubicará en la primera posición del arreglo y en el peor de lo casos, la persona no se encontrará en el arreglo.

En expresiones Matemáticas esta es la expresión Lineal:

f(x)=x

En notación Big-O se expresa de la siguiente manera:

O(n)

Como lo expresan las ecuaciones, cuanto más elementos tenga el arreglo, más tiempo va a demorar en encontrar personas.

Constantes: Supongamos que tenemos una Tabla Hash (Hashtable) cuya responsabilidad propósito es devolver el valor en base a una clave

Entonces si tenemos la siguiente Tabla Hash

const colores = ["Blanco", "#FFFFFF"	], ["Rojo", "#FF0000"], ["Negro", "#000000"] , ["Amarillo", "#FFFF00"],  ["Verde", "#008000"]

Por cada vez que intente recuperar un valor, en base a una clave, el tiempo de respuesta será siempre el mismo

const colorBalnco = colores["Blanco"]
	// resultado #FFFFFF
const colorVerde = colores["Verde"]
// resultado "#008000"
const colorAzul = colores["Azul"]
// resultado Undefined

En expresiones Matemáticas esta es la expresión Constante:

f(x)=c

En notación Big-O se expresa de la siguiente manera:

O(1)

Las gráficas de estas dos notaciones se pueden ver a continuación

Partition Structure

Algunas preguntas típicas que se hacen sobro estas anotaciones

  • ¿Que sucede si mi procesador es antiguo?
  • ¿Que sucede si tengo un procesador muy rápido?
  • ¿Que sucede si mi procesador tarda en cargar, y luego arranca la ejecución?

La respuesta a estas preguntas son las mismas para las tres

La ecuación no cambia, tal vez

f(x)=x demorando la mitad, será ==> f(x)=1/2x o demorando el doble será ==> f(x)= 2x O demorando en iniciar, será ==> f(x) = 2+x

Pero siempre la ecuación es f(x)=x

Con lo cual se la considera lineal y lo mismo aplica para la constante, puede ser f(x) = 1 o f(x) = 1/2 o f(x)=2 pero siempre será f(x)=c

Estas son las dos notaciones más simples de entender de Big O.

En el próximo Post voy a hablar de las expresiones cuadráticas y de cualquier exponte.