zusammenfassender Begriff, um das Verhalten von Algorithmen zu charakterisieren, darunter den Ressourcenverbrauch wie worst case-Rechenzeit, average case-Rechenzeit und Raumkomplexität, aber auch Eigenschaften, wie die Güte (Güte eines Algorithmus).

Um die Effizienz von Algorithmen beurteilen zu können, braucht man einen Maßstab, an dem man diese Effizienz messen kann. Man konzentriert sich dabei auf die Betriebsmittelressourcen Laufzeit und Speicherbedarf. Die Komplexität eines Algorithmus beschreibt daher, welches Laufzeitverhalten der Algorithmus haben und in welchen Größenordnungen sich sein Speicherplatzbedarf bewegen wird. Damit verfügt man über eine Möglichkeit, die Kosten eines Algorithmus abzuschätzen. In der Regel bestimmt man die Komplexität in Abhängigkeit von bestimmten Parametern, die die Größenordnung der Inputdaten beschreiben. Geht es beispielsweise um die Verarbeitung von (n × n)-Matrizen, so wird man die Komplexität des jeweiligen Algorithmus als Funktion in Abhängigkeit von n ausdrücken. Für die Berechnung der Koeffizienten eines univariaten Polynoms vom Grad n aus seinen Nullstellen ist etwa der Grad ein geeigneter Maßstab. (Die Zahl n log n ist hier eine untere Schranke für die Anzahl der Multiplikationen und Divisionen).

Dabei ist der Begriff der Ordnung von großer Bedeutung. Man sagt, die Laufzeitkomplexität eines Algorithmus ist von der Ordnung g(n) und schreibt T(n) = O(g(n)), wenn es eine Zahl k ∈ ℕ gibt, so daß die Anzahl der im Algorithmus duchgeführten Operationen kleiner oder gleich k · g(n) ist. Dabei ist man häufig an Algorithmen mit polynomialem Laufzeitverhalten interessiert, also an Ordnungen der Art O(n) oder O(n²).