[Algoritmi, complessità counting sort]

[zio_mangrovia]

In questo algoritmo non capisco la complessità $O(n+k)$, in particolare se terzo for non ci fosse la complessità dell'algoritmo sarebbe ugualmente $O(n+k)$ ?
La complessità non dovrebbe essere $O(max(n,k))$ che a mio avviso non è la stessa cosa di $O(n+k)$,
dove sbaglio?

[probid]

"zio_mangrovia":$O(max(n,k))$ che a mio avviso non è la stessa cosa di $O(n+k)$

https://math.stackexchange.com/questions/291465/formally-prove-that-theta-maxf-g-thetafg/

Ciao!

[zio_mangrovia]

"probid":
https://math.stackexchange.com/questions/291465/formally-prove-that-theta-maxf-g-thetafg/

Grazie 1000.
Ma il terzo for preso da solo ha complessità $O(k)$ ? E' corretto?

[vict85]

"zio_mangrovia":[quote="probid"]
https://math.stackexchange.com/questions/291465/formally-prove-that-theta-maxf-g-thetafg/

Grazie 1000.
Ma il terzo for preso da solo ha complessità $O(k)$ ? E' corretto?[/quote]

No. Devi ragionare sul while. La somma dei valori dell'array C è uguale a \(n\), quindi quel while è vero per \(n\) volte ed è falso per \(k\) volte (ad un certo punto diventa falso ed esce dal ciclo).

[zio_mangrovia]

"vict85":
No. Devi ragionare sul while.
La somma dei valori dell'array C è uguale a \(n\)

Questo è ok.

quindi quel while è vero per \(n\) volte ed è falso per \(k\) volte (ad un certo punto diventa falso ed esce dal ciclo).

Non mi torna tanto...
Il while è vero per \(n\) volte però solo complessivamente: per ogni iterazione del for il while può essere vero ma per un numero limitato di valori che può non essere \(n\)

k=4
n=10
i=0 while vero per 1 volte
i=1 while vero per 0 volte
i=2 while vero per 4 volte
i=3 while vero per 5 volte
i=4 while vero per 0 volte

E' vero che alla fine complessivamente ho \(n\) iterazioni ma anche \(k\) dettate dal for, no?
Allora qual è la complessità di quest'ultima parte ?

[vict85]

Quello che intendevo è che la condizione del while viene calcolata complessivamente \(n+k\) volte, di cui n vere e k false.