Implementazioni di algoritmi/Radix sort: differenze tra le versioni

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.
 
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==
1

contributo