ein Algorithmus, dessen worst case Rechenzeit durch ein Polynom in der Eingabelänge beschränkt ist.

In der Komplexitätstheorie gelten polynomiale Algorithmen als effizient. Dies läßt sich aus Sicht der Anwendungen nur rechtfertigen, wenn der Grad des Polynoms für die Rechenzeit klein genug ist.