La idea de medir el tiempo y espacio como una función de la longitud de la entrada se originó a principios de los 60's por Hartmanis y Stearns, y así nació la teoría de la complejidad computacional.