Die algorithmische Komplexität eines Problems ist die Anzahl an elementaren Rechenschritten, die ein optimaler Algorithmus für dieses Problem im schlechtesten Fall aufwenden muss. Sie wird auch als worst case-Laufzeit bezeichnet.
Die Schwierigkeit liegt darin, dass man somit alle Algorithmen für ein Problem betrachten müsste, um die Komplexität des selben zu bestimmen. So bedeutet eine Komplexität des Problems P von f(n) (bei Eingabelänge n), dass jeder Algorithmus der P löst, mindestens eine Rechenzeit von f(n) benötigt, es aber auch ein Algorithmus existiert, welcher P in f(n) Schritten löst.
Ein Problem A, welches mit geringem Aufwand auf ein Problem B zurückgeführt werden kann, gehört mindestens zur Komplexitätsklasse von B. B wird dann härter als A genannt. Ein Problem A ist k-hart, wenn sich alle anderen Probleme der Klasse k auf A zurückführen lassen. Liegt ein k-hartes Problem A selbst in der Klasse k, wird es k-vollständig genannt.
Beispiel: Rasenmähen hat lineare Komplexität (in der Fläche), 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 -- siehe binäre Suche).
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 den Artikeln Komplexitätstheorie und asymptotische Laufzeit.