Hartmanis ja Stearns julkaisivat vuonna 1965 kuuluisan artikkelin On The Computational Complexity of Algorithms.[2][3] Hartmanis ja Stearns olivat kiinnostuneita paljonko aikaa ja muistia erilaisiin laskuihin vaaditaan, jonka he ovat ovat nimenneet laskennalliseksi kompleksisuudeksi.[2]