Landau-Klassen

Notation	Bedeutung	Anschauliche Erklärung	Beispiele für Laufzeiten
f ∈ O(1)	f ist beschränkt	f überschreitet einen konstanten Wert nicht (unabhängig vom Wert des Arguments).	Nachschlagen des n-ten Elementes in einem Feld.
f ∈ O(log n)	f wächst logarithmisch	f wächst ungefähr um einen konstanten Betrag, wenn sich das Argument verdoppelt. Die Basis des Logarithmus ist dabei egal.	Binäre Suche im sortierten Feld mit n Einträgen
f ∈ O(n)	linear	f wächst ungefähr auf das Doppelte, wenn sich das Argument verdoppelt.	Suche im unsortierten Feld mit n Einträgen (Bsp. Lineare Suche)
f ∈ O(n ∗ log n)	f hat super-lineares Wachstum		Fortgeschrittenere Algorithmen zum Sortieren von n Zahlen Mergesort, Quicksort (im Average Case)
f ∈ O(n2)	quadratisch	f wächst ungefähr auf das Vierfache, wenn sich das Argument verdoppelt	Einfache Algorithmen zum Sortieren von n Zahlen Selectionsort
f ∈ O(n!)	f wächst mit der Fakultät	f wächst ungefähr auf das (n+1)-fache, wenn sich das Argument um eins erhöht.	Problem des Handlungsreisenden