In de
complexiteitstheorie kan een
algoritme in
polynomiale tijd uitgevoerd worden als de benodigde tijd, als functie van de grootte van de invoer, begrensd wordt door een
polynoom. Polynomiale tijd wordt vaak genoteerd als O(
nk) waarbij
n de grootte van de invoer weergeeft en
k een constante die per probleem kan verschillen. Zie
complexiteitsgraad voor een definitie en een toelichting bij deze notatie.