Laufzeit InsertionSort/Countsort (Worst Case)?

Sei n die Eingabgelänge des Arrays und k die Größe des Wertebereichs .

Es gelte, dass k=n

 ist. Somit wächst die Größe des Wertebereichs linear mit der Größe der Eingabe. 

Welcher der beiden Algorithmen (Insertionsort bzw. Countsort) weist für große n im Worst Case unter diesen Annahmen eine bessere Laufzeit auf?

Kann ich auch eine Begründung kriegen, oder mir erklären was ich machen muss um das rauszufinden ?

Answer 1

[Destranix]

Insertionsort hat immer dieselbe Worst-Case-Laufzeit in Abhängigkeit von n.
Bei einem klassischem Insertion-Sort ist das O(n²) (oder eher nach der Gaußschen Summenformel O((n * (n+1))/2)).

Countsort muss einmal den Array durchlaufen, um die Counts zu bestimmen (O(n)) und dann für jeden Wert des Wertebereichs den Wert entsprechend oft in den Ausgabearray schreiben ((O(k)).
Entsprechend hat eine klassische Implementierung immer die Laufzeit O(n + k), auch im Worst-Case.

Das wäre dann im Vergleich O(n²) gegen O(2n). Damit sollte sich deine Aufgabe beantworten lassen.

Zu beachten sie allerdings, dass die zusätzliche Speicherplatzkomplexität bei Countingsort O(k) ist, während sie bei Insertionsort O(1) sein kann.