Algorithmes de complexité polynomiale $\mathcal {O}(n^k)$, $k$ fixé

Nous appelons ainsi tous les algorithmes dont le temps d'exécution peut être majoré par un polynôme. Nous utiliserons le terme polynomial par opposition à exponentiel. En algorithmique, il sera très important de faire la différence entre les algorithmes polynomiaux, utilisables en pratique, et les algorithmes exponentiels, inutilisables en pratique.