Komplexität - Beispiel

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

0 + 1 + 2 +...+ (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 zu kaufen lohnt sich kaum, man gewinnt damit nur einen konstanten Faktor. Viel wirksamer sind bessere Algorithmen!