BigO Notation
What is BigO Notation?
La Big O Notation es una forma de medir que tan eficiente es un algoritmo en función de cuantos argumentos necesita.
No mide el tiempo en segundos reales sino que mide el costo de tiempo o de memoria cuando la entrada o argumento crece.
Why do we need BigO Notation?
Cuando escribimos un algoritmo, queremos saber que tan eficiente es, y para eso necesitamos una forma de medirlo. La Big O Notation nos permite medir el costo de tiempo o de memoria de un algoritmo en función de su entrada.
En pocas palabras:
Si probaste el algoritmo con 10 argumentos y tardo 1 segundo, no significa que si lo pruebas con 100 argumentos va a tardar 10 segundos. Puede ser que tarde 2 segundos, o 5 segundos, o incluso 20 segundos o hasta en casos extremos una hora. La Big O Notation nos permite entender como el algoritmo se tiene que comportar cuando la entrada crece.
En palabras nerds:
Big-O describe el comportamiento asintótico de un algoritmo o una operación: cómo crece el tiempo (o espacio) requerido a medida que crece el tamaño del input n, en el peor caso.
Qué clases de Big-O existen?
Existen muchas clases de Big-O, pero las más comunes son:
| Notación | Nombre | Ejemplo típico |
|---|---|---|
| O(1) | Constante | Acceso por índice en array |
| O(log n) | Logarítmica | Búsqueda binaria, operaciones en BST balanceado |
| O(n) | Lineal | Recorrer una lista |
| O(n log n) | Linealítmica | MergeSort, HeapSort |
| O(n²) | Cuadrática | Bubble sort, comparación de todos los pares |
| O(2ⁿ) | Exponencial | Algoritmos de fuerza bruta sobre subconjuntos |
Próximos temas
En la siguiente unidad aprenderás sobre complejidad amortizada, que es fundamental para entender cómo se comportan las estructuras dinámicas como los arrays dinámicos.