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 ?