Aufwandsabschätzung im Detail

Im Abschnitt zur binären Suche haben wir uns bereits einige Gedanken zur Aufwandsabschätzung gemacht.

Eine Besonderheit des QuicksortAlgorithmus ist, dass er Aufwand von der Wahl des Pivotelement abhängt.

Um ein Gefühl dafür zu bekommen, was die gängigsten Laufzeitcharakteristiken bedeuten, können die folgenden Beispiele dienen:

10 Elemente	100 Elemente	1000 Elemente
O(log n)	0,15 Sekunden	0,3 Sekunden	0,5 Sekunden
O(n)	0,5 Sekunden	5 Sekunden	50 Sekunden
O(n log n)	1,6 Sekunden	33 Sekunden	490 Sekunden
O(n2)	5 Sekunden	5s	8Min