Calculadora de Complejidad Big-O

Cuenta cuántas veces se ejecuta cada instrucción en función del tamaño de la entrada. Los bloques secuenciales toman el máximo de sus costes; los bloques anidados se multiplican. Un bucle que suma una cantidad fija a su contador es lineal; uno que lo multiplica o lo divide es logarítmico. Una función recursiva se resuelve por su recurrencia: dos llamadas sobre la mitad de la entrada más trabajo lineal dan n log n, y dos llamadas sobre n − 1 dan 2^n. Esta calculadora aplica exactamente esas reglas y muestra cada aplicación junto a un número de línea.

Big O es una cota superior: dice que el trabajo no crece más deprisa que la función indicada. Lo más habitual es darla para el peor caso, y eso es lo que informa esta calculadora: un bucle que puede terminar antes se cuenta igualmente completo, y el panel de límites lo indica. El mejor caso es otra pregunta, que suele escribirse con Big Omega (Ω).

Big O es una cota superior (no crece más deprisa que), Big Omega (Ω) una cota inferior (crece al menos tan deprisa como) y Big Theta (Θ) las dos a la vez, una cota ajustada. La ordenación por mezcla es Θ(n log n): nunca mejor ni peor que n log n. La ordenación por inserción es O(n²) en el peor caso pero Ω(n) en el mejor, así que ninguna Θ única cubre todas sus entradas. La calculadora informa la Big O del peor caso.

Python, JavaScript y TypeScript, Java, C y C++, C# y Go. La detección es automática, tanto a partir de un método suelto como de un archivo entero, y puedes cambiarla. El análisis es estructural en lugar de un análisis sintáctico completo, así que también funciona con un fragmento incompleto: el cuerpo de un bucle pegado sin la función que lo contiene se lee correctamente.

Para las formas de bucle, recursión y biblioteca que reconoce, sí, y además muestra su desarrollo para que puedas confirmarlo. Se comprueba con más de cien algoritmos de libro de texto y de entrevistas técnicas en seis lenguajes. Lo que no puede ver es el comportamiento que depende de los datos: un bucle que casi siempre termina antes de tiempo, una tabla hash que degenera en una lista con claves adversas, o una lista que el código sigue haciendo crecer dentro de su propio bucle. Todo eso se declara como límite, sin incorporarlo en silencio a la respuesta.

La complejidad temporal cuenta operaciones a medida que crece la entrada; la espacial cuenta memoria. Con frecuencia se intercambian entre sí: memoizar una función recursiva convierte un tiempo exponencial en lineal a costa de un espacio lineal. Leer solo una de las dos oculta el precio de la otra, y por eso aquí se muestran ambas.

O(1), tiempo constante: el trabajo no crece con la entrada. Le siguen O(log n) y O(√n), y después O(n). Que se pueda alcanzar una clase mejor depende del problema; por ejemplo, ninguna ordenación por comparación baja de O(n log n) en el peor caso.

La misma idea aplicada a funciones cerca de un punto o en el infinito. En cálculo, f(x) = O(g(x)) cuando x → 0 significa que |f(x)| ≤ C·|g(x)| cerca de cero; el término de error de una serie de Taylor, sen x = x − x³/6 + O(x⁵), es el uso clásico. El análisis de algoritmos usa la versión en el infinito: cómo crece el trabajo cuando n se hace grande.

El espacio auxiliar es la memoria que un algoritmo reserva además de la entrada que recibió. Una ordenación in situ es O(1) auxiliar aunque el arreglo que ordena tenga n elementos, porque no reservó ese arreglo. Es la convención que se usa en las entrevistas y en la mayoría de los libros de texto.

Porque los dos bucles recorren colecciones distintas. Sus tamaños son independientes, así que el coste es el producto de dos dimensiones separadas, y reducirlo a n² afirmaría una relación que el código no contiene. Por la misma razón, dos bucles sobre ellas uno detrás de otro son O(n + m). Las etiquetas bajo el resultado indican a qué variable corresponde cada símbolo.

No. El análisis se ejecuta en tu navegador. No se envía nada a un servidor, que es también la razón de que no haya espera por una respuesta ni límite de uso.