Sei T(n) die Anzahl auszuführender elementarer Operationen in Abhängigkeit von der Größe n der Eingabe, dann ist T(n) eine Beschreibung für die Laufzeit des Algorithmus.

Es gilt:

positive Funktion: T(n) > 0
positive Anzahl an Elementaroperationen: n > 0

Die Lösung eines Problems dauert immer länger als 0 Sekunden.

Landau-Symbole

Eine positive Funktion T(n) heißt O(f(n)), wenn es ein n₀ gibt, so dass
T(n) ≤ c₂ · f(n) für n ≥ n₀; c₂ > 0

Dann ist T(n) Element von O(f(n)), man schreibt T(n) = O(f(n)) “groß Oh von f von n”.

Beispiel:
Sei T(n) = 4 n²+n
Dann ist T(n) = O(f(n)) mit f(n) = n³, also T(n) = O(n³)
Aber es gilt auch: T(n) = O(n²)

Um in diesem Fall genauer zu differenzieren, wird ein weiteres Symbol eingeführt:

Wenn c₁ · f(n) ≤ T(n) ≤ c₂ · f(n) für alle n > n₀, dann ist die Abschätzung “scharf” und wir schreiben:

T(n) = Θ(f(n))

Anwendung auf Selection Sort

Durch die äußere Schleife entstehen n-1 Durchläufe, also O(n). Durch die innere Schleife entstehen je nach aktuellem Stand der äußeren Schleife unterschiedlich viele Durchläufe, im Mittel n/2 Durchläufe, also O(n). Durch die Zuweisungen nach der Schleife entstehen weitere c Operationen. Diese können wir aber vernachlässigen. Da die Schleifen ineinander verschachtelt sind, müssen wir ihre Laufzeiten multiplizieren und erhalten: O(n²)

Typische Laufzeitverhalten von Algorithmen

• O(log(n)) → logarithmische Laufzeit, Optimum
• O(n) → lineare Laufzeit, z.B. Vergleiche
• O(n · log(n)) zum Beispiel Sortieralgorithmen
• O(n²) → quadratische Laufzeit
• O(n^p) → polynomiale Laufzeit
• O(aⁿ) → exponentielle Laufzeit, nicht realisierbar für größere Eingaben