Komplexität - Beispiel

Sortieren durch lineares Einfügen (Bubblesort, bzw. entsprechendes Netzwerk) benötigt für $n$ Elemente

$$0 + 1 + 2 + \ldots + (n-1) = (n-1)n/2$$

Vergleiche.

Egal, auf welchem Rechner wir das ausführen, die Laufzeit wird immer eine quadratische Funktion der Eingabegröße sein.

D. h. Eingabegröße verdoppeln $\to$ vierfache Laufzeit, verdreifachen $\to$ neunfache, usw.

Schnelleren Prozessor kaufen lohnt sich kaum, man gewinnt damit nur einen konstanten Faktor. Viel wirksamer sind bessere Algorithmen!