Musteraufgabe

Im Normalfall kommen folgende Laufzeitkomplexitäten vor:

O(1)	Konstante Laufzeit, d.h. die Laufzeit ist komplett unabhängig von den Eingabedaten (Beispiel: Berechnung der Fläche eines Rechtecks).
O(log N)	Die Laufzeit steigt proportional zum Logarithmus von N. Dies ist meist bei etwas komplizierteren Algorithmen der Fall, so zum Beispiel bei der "binären Suche".
O(N)	Die Laufzeit steigt proportional zur Eingabegröße. Verdoppelt sich die Eingabegröße, verdoppelt sich die Laufzeit. Dies ist z.B. der Fall bei der Suche des Maximums von N verschiedenen, unsortierten Werten.
O(N log N)*	Die Laufzeit steigt proportional zur Funktion Nlog N*. Hier handelt es sich wieder um Algorithmen, deren Laufzeit etwas schwieriger zu bestimmen ist, so z.B. das Sortieren einer Liste von Zahlen mit dem Mergesort Algorithmus.
O(N^2)	Die Laufzeit steigt mit dem Quadrat der Eingabegröße. Verdoppelt sich die Eingabe, vervierfacht sich die Laufzeit. Wir werden weiter unten einen Algorithmus mit quadratischer Laufzeit kennenlernen.
O(N^3)	Die Laufzeit steigt mit der Funktion N^3, so wie bei dem oben aufgelisteten Programm.