polynomiale tijd

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(n^k) 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.