auch kurz Komplexität, die Schwierigkeit eines Problems bzgl. eines vorgegebenen Komplexitätsmaßes wie z. B. der worst case Rechenzeit, average case Rechenzeit, der Schaltkreiskomplexität oder der Raumkomplexität.

Die Komplexität ist gleich einer Funktion f(n), wobei n die Eingabelänge bezeichnet, wenn es einen Algorithmus oder eine Realisierung gibt, für die die Ressourcen asymptotisch durch O(f(n)) beschränkt sind, und es keine Möglichkeit gibt, mit durch o( f(n)) beschränkten Ressourcen auszukommen.

Oftmals sind nur untere und obere Schranken für die Komplexität bekannt. Polynomielle Komplexität beschreibt eine obere Schranke für die Komplexität, die durch eine polynomiell wachsende Funktion gegeben ist. Exponentielle Komplexität beschreibt eine untere Schranke für die Komplexität, die durch eine exponentiell wachsende Funktion gegeben ist.