Calculadora de complejidad Big O: operaciones y tiempo estimado🌎

La calculadora evalúa la función matemática correspondiente a cada complejidad para el valor de n ingresado: O(1) → 1 operación, O(log n) → log₂(n) operaciones, O(n) → n, O(n log n) → n × log₂(n), O(n²) → n², O(2^n) → 2^n. Luego divide el resultado por 10⁹ (operaciones por segundo de una CPU moderna como referencia estándar) para obtener segundos. Es una estimación de orden de magnitud, no una medición real: el tiempo real depende del hardware, el lenguaje, el compilador, la caché y las constantes ocultas del algoritmo. Usala para comparar alternativas, no para predecir tiempos de producción al milisegundo.

O(1) significa que la operación tarda lo mismo sin importar el tamaño de los datos. Ejemplos clásicos: acceder a un elemento de array por índice (arr[42]), buscar en un hash map o diccionario, hacer push o pop en un stack, leer o escribir una variable. En CPU moderna son operaciones de nanosegundos constantes. El error común es pensar que O(1) es siempre 'instantáneo': una operación O(1) con una constante enorme puede ser más lenta que O(n) con n pequeño. Big O solo describe cómo escala, no la velocidad absoluta.

O(log n) aparece cuando cada paso del algoritmo descarta la mitad del problema restante. El ejemplo canónico es la búsqueda binaria: en un array de 1.000.000 de elementos ordenados, necesitás como máximo 20 comparaciones (log₂ de 1M ≈ 20). Si duplicás el array a 2M, solo agregás 1 comparación más. En código se produce en: búsqueda binaria, árboles binarios balanceados (AVL, Red-Black), estructuras heap, e índices B-tree en bases de datos relacionales. Para n=1M: O(n) son 1M ops; O(log n) son 20 ops. La diferencia es de cinco órdenes de magnitud.

Depende del contexto, pero como referencia general con CPU a 10⁹ ops/s: n=1.000 → 1 ms (imperceptible), n=10.000 → 100 ms (notable para el usuario), n=100.000 → 10 segundos (inaceptable en un endpoint web), n=1.000.000 → casi 17 minutos (inviable). El problema es que muchos sistemas arrancan con datasets pequeños donde O(n²) funciona, y el cuello de botella aparece seis meses después cuando el cliente tiene 10× más datos. Si el dominio puede crecer a 10.000 ítems o más, vale la pena buscar una solución O(n log n). En Python puro el límite práctico de O(n²) baja a n=1.000–3.000 por el overhead del intérprete.

O (Big O) es la cota superior: el peor caso posible. Ω (Omega) es la cota inferior: el mejor caso. Θ (Theta) es cota ajustada: el algoritmo crece exactamente así en todos los casos. Ejemplo con quicksort: su peor caso es O(n²) cuando el pivote siempre elige el extremo; su promedio es Θ(n log n). En entrevistas técnicas, cuando alguien dice 'la complejidad es...', casi siempre se refiere a O (peor caso). Mergesort es Θ(n log n) en todos los casos, por eso es preferido cuando la consistencia importa más que la velocidad promedio.

Seguí estas reglas prácticas: un loop simple sobre n elementos → O(n). Dos loops anidados sobre n → O(n²). Tres loops anidados → O(n³). Un loop que en cada iteración divide n a la mitad → O(log n). Una función recursiva que se llama a sí misma dos veces sin memoización → O(2^n). Recursión que divide y combina (mergesort) → O(n log n). Las constantes y términos de menor orden se ignoran: O(3n + 5) se simplifica a O(n). Si tenés un loop O(n) seguido de otro O(n), el resultado sigue siendo O(n), no O(2n).

La calculadora asume 10⁹ operaciones/segundo, que es la referencia estándar para código compilado (C, C++, Rust, Java JIT). Python interpretado ejecuta aproximadamente 10⁷ operaciones simples por segundo, unas 100 veces más lento. Entonces para Python puro, multiplicá el tiempo estimado por 100. Un O(n²) con n=10.000 que la calculadora muestra como 0,1 s, en Python tarda ~10 s. Por eso NumPy, Pandas y PyTorch delegan los loops pesados a extensiones en C: recuperan los 10⁹ ops/s para las operaciones críticas.

Big O también se usa para medir memoria, no solo tiempo. Merge sort es O(n log n) en tiempo pero O(n) en espacio extra porque necesita arrays auxiliares. Quicksort in-place es O(log n) en espacio (solo el stack de recursión). Cuando construís una tabla de hash para resolver un problema en O(n) tiempo, normalmente usás O(n) espacio adicional. En sistemas embebidos, funciones Lambda con límites de RAM, o móviles con poca memoria, el trade-off tiempo-espacio importa tanto como el tiempo de ejecución.

Porque el crecimiento exponencial supera cualquier mejora de hardware. Con n=50, tenés 2^50 ≈ 10¹⁵ operaciones. A 10⁹ ops/s son ~11,6 días. Con una CPU 1000 veces más rápida serían ~16 minutos, lo que sigue siendo inviable en producción. Con n=100, son 2^100 ≈ 10³⁰ operaciones: ninguna computadora puede con eso. La solución no es hardware más rápido sino algoritmos con poda (branch and bound), programación dinámica, o aproximaciones. Para n ≤ 20–25, O(2^n) sigue siendo manejable en muchos contextos.

Sí, y es uno de los errores más comunes optimizar prematuramente basándose solo en Big O. Las constantes ocultas importan cuando n es pequeño: insertion sort O(n²) es más rápido que merge sort O(n log n) para n < 10–20 elementos porque tiene menos overhead. De hecho, muchas implementaciones de sort en Python (Timsort) y Java usan insertion sort internamente para subarrays pequeños. Big O te da el mapa general; el profiling en producción con datos reales te da el territorio exacto.

La estrategia más útil es calcular los dos o tres algoritmos candidatos con el n máximo esperado en producción. Primero estimá el volumen: si tenés 50.000 registros hoy y el negocio crece 3× por año, en dos años estarás en 450.000. Calculá el tiempo para n=450.000 con cada alternativa. Si la diferencia es de milisegundos vs minutos, tenés un argumento sólido para priorizar el refactor. También identificá correctamente qué es n en tu problema: puede ser el número de nodos en un grafo, la longitud de un string, o el tamaño de un batch, no necesariamente el total de registros.

El análisis amortizado describe el costo promedio de una operación a lo largo de una secuencia, no el costo individual en el peor caso. El ejemplo clásico es el array dinámico (ArrayList en Java, vector en C++, list en Python): insertar al final es O(1) amortizado aunque ocasionalmente sea O(n) cuando hay que redimensionar. Si analizás n inserciones consecutivas, el total es O(n), entonces el promedio es O(1) por operación. Esta calculadora trabaja con el análisis de peor caso estándar (Big O clásico), que es lo más relevante para comparar algoritmos entre sí.