Big O Notation

La notación O grande describe el límite superior asintótico de una función, usada para analizar la complejidad temporal/espacial de los algoritmos ignorando constantes y términos de orden inferior.

Propósito

Abstraer la tasa de crecimiento asintótico de la eficiencia de un algoritmo para comparar y elegir algoritmos.

Mecanismo

f(n)=O(g(n)) significa que existen constantes C y n0 tales que |f(n)|≤C|g(n)| para todo n>n0. Órdenes comunes: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n) < O(n!). Se centra en cotas superiores del peor caso.

Casos de uso

Análisis de complejidad de algoritmos
Selección de estructuras de datos
Decisiones de optimización de rendimiento
Entrevistas y docencia

Ejemplos

entrada
```
Binary search
```
Output
```
O(log n)
```
Halves each time

Errores comunes

Ignoring constant factors misjudges real-world performance: Big O is asymptotic; benchmark for real behavior

Términos relacionados

Sorting Algorithm

Los algoritmos de ordenación disponen los elementos en orden —quicksort, merge sort y heapsort son comunes— con complejidades que van de O(n log n) a O(n²).

La búsqueda binaria compara contra el elemento central de un array ordenado y reduce el rango a la mitad cada vez, localizando un objetivo en O(log n); es el algoritmo de búsqueda eficiente fundamental.

Una tabla hash mapea claves a un array de cubos mediante una función hash, ofreciendo búsqueda/inserción/borrado promedio O(1); es una de las estructuras de datos más usadas.

References