Implementazioni di algoritmi/Radix sort: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
Riga 16:
La precedente definizione è dimostrabile ricordando che ci sono <math>log_n (k) = \mathcal{O}(log_n (k))</math> passate di [[Integer sort]] e ciascuna richiede tempo <math>\mathcal{O}(n)</math>.
 
Usando le regole per il cambiamento di base dei [[logaritmo|logaritmi]], il tempo totale è dato da <math>\mathcal{O}(n log_n (k)) = \mathcal{O}(n {log (k) \over log (n)})</math>.

A questa quantità va aggiunto <math>\mathcal{O}(n)</math> per contemplare il caso in cui k < n, dato che la sequenza, va almeno letta.
 
==Implementazione in Java==