Originariamente inviato da matrics
quello che hai scritto è il counting sort, di costo lineare, non capisco come vederlo di costo logaritmico
Se usi un criterio di costo costante, dove ogni istruzione ha un costo fisso e non dipende dai dati manipolaiti, il costo è O(n)

se invece per valutare il costo usi un criterio di costo logaritmico, dove ogni istruzione ha un costo variabile in base alla dimensione dei dati trattati (i dati sono numeri rappresentati in binario --> dimensione = log(n)), il costo viene O(nlog(m))



in questo caso comunque, essendo che i dati hanno una lughezza fissata da un limite superiore, è + ragionevole utilizzare il criterio di costo costante. (dalle mie riminescenze di info teorica)