Die Komplexität ist ein formaler Begriff, der die "Geschwindigkeit" eines Algorithmus beschreibt. Dabei kommt es nicht auf die effektive Ausführungszeit (z.B. in Sekunden) an, da diese ja von der speziellen Implementierung und der Rechenleistung des verwendeten Computers abhängig ist, sondern darauf, wie sich diese in Abhängigkeit einer Eingangsgröße verhält. Diese Eingangsgröße ist meistens die Größe der Eingangsdaten (genauer, die Eingabelaenge der Eingabeinstanz).
Beispiel: Rasenmähen hat lineare Komplexität, denn bei doppelter Rasenfläche braucht man auch doppelt so lange. Suchen im Telefonbuch hat hingegen nur logarithmische Komplexität, denn bei doppelt so dickem Telefonbuch schlägt man dieses nur einmal öfter auf (z.B. genau in der Mitte - dann hat man das Problem auf die Hälfte reduziert).
Es kommt auch vor, dass nicht das Zeitverhalten des Algorithmus betrachtet wird, sondern z.B. der Speicherbedarf oder irgend ein anderer Bedarf an Ressourcen.
Zur mathematischen Formulierung der Komplexität bedient man sich des Landau-Symbols O. Es steht z.B. O(N) für lineare Komplexität, O(N2) für quadratische usw.
Genaueres findet man in der Komplexitätstheorie.