---

Geschrieben von jordy am 12.01.2016 um 11:44:

  CountingSort Laufzeit

Meine Frage:
Algorithmus :
For i <- 0 to k do C[r] <- 0
For i <- 1 to n C[A[i]] <- C[A[i-1]] + C[A[i]]
For r <- 1 to k do C[r ] C[r 1048576- 1] + C[r ]
For i <- n downto 1 do B[C[A[i ]]] <- A[i ],
C[A[i ]] C[A[i ]] - 1048576 1.

Die Laufzeit ist Theta(n+k). Warum ?

Meine Ideen:
Ich zähle zur Laufzeitbestimmung doch die Anazhl der ausgeführten For-Schleifen .
Für Theta(n+k) würde man doch aber nur die zweite und dritte Schleife berücksichtigen ?

---

Geschrieben von eulerscheZahl am 12.01.2016 um 16:52:

 

Du hast 4 Schleifen, 2 mit Laufzeit Theta(n) und 2 mit Theta(k).
Die Gesamtlaufzeit wird durch die größte Einzelzeit bestimmt. Da du aber nicht weißt, ob n oder k größer ist, eben Theta(n+k). Es würde auch Theta(max(n, k)) gehen.