Notación Big-O

Con la notación Big-O buscamos descubrir una función (constante, lineal, polinomial, logarítmica y exponencial) que sea mayor o igual que la complejidad de un algoritmo, es decir, el peor caso que puede ejecutarse el programa.

Clases de Big-O

Las clases de Big-O son las representaciones simbólicas del tipo de crecimiento del algoritmo en el peor de los casos. El tipo de crecimiento es la función que se aproxima a los resultados de los valores de tiempo o espacio.

Esta representación simbólica consiste en la letra O mayúscula seguida de paréntesis que incluyen el tipo de crecimiento.

De esta manera, ya conoces las funciones representadas en la siguiente gráfica, donde las peores complejidades están situadas al extremo superior izquierdo, y las mejores están en el extremo inferior derecho. De las cuales representan el rendimiento del algoritmo.

Fuente: Big-O Cheat Sheet

Contribución creada por Andrés Guano (Platzi Contributor).