Una caracterización de la tasa de crecimiento del tiempo de ejecución de un algoritmo en función del tamaño de la entrada, típicamente expresada asintóticamente (p. ej., Big O) para comparar escalabilidad.

Principio

El uso de recursos se abstrae en funciones del tamaño de entrada de modo que los términos dominantes determinan el comportamiento asintótico, permitiendo comparaciones independientes de constantes dependientes de la máquina.

Demostración

Quicksort tiene complejidad temporal media O(n log n), mientras que el ordenamiento por inserción tiene peor caso O(n^2); para n grandes, Quicksort escala mejor a pesar de factores constantes.

Aplicación incorrecta

Usar Big O como tiempo exacto de ejecución, ignorar las distinciones entre caso medio y peor caso, o seleccionar algoritmos únicamente por clase asintótica cuando importan constantes y distribuciones de entrada.

Consecuencia

Su uso apropiado informa la elección de algoritmos, predice tendencias de rendimiento para entradas grandes y guía los compromisos teóricos de complejidad en diseño y optimización.

Inversión

Centrarse exclusivamente en factores constantes y microbenchmarks sin considerar el crecimiento asintótico, lo que puede ocultar una mala escalabilidad para entradas grandes.

Límite

Se refiere al tiempo como un recurso abstracto medido respecto al tamaño de la entrada; excluye detalles dependientes de la implementación, optimizaciones específicas de hardware y recursos no temporales como memoria o energía (salvo inclusión explícita).

Tensión semántica

Suele confundirse con tiempo de ejecución empírico o 'eficiencia'; la complejidad temporal es una abstracción asintótica basada en un modelo, no una métrica de rendimiento exacta.

Síntesis

La complejidad temporal algorítmica es la descripción asintótica de cómo crece el tiempo de ejecución de un algoritmo con el tamaño de la entrada, usada para evaluar escalabilidad y guiar la elección de algoritmos bajo modelos de coste idealizados.