Confrontiamo la complessità in tempo degli algoritmi di ordinamento ingenui con quella degli algoritmi evoluti, al variare della dimensione del problema
| n | n2 (ingenuo) | nlog2n (evoluto) | evoluto / ingenuo |
| 103 | 106 | ~104 | 10-2 |
| 106 | 1012 | ~2*107 | 2*10-5 |
| 109 | 1018 | ~3*1010 | 3*10-8 |
| 1010 | 1020 | ~3,3*1011 | 3,3*10-9 |
Moltiplicando per 103 il numero di elementi nel vettore, si moltiplica per 106 il numero di operazioni dell’algoritmo ingenuo (per ~104 il numero di operazioni dell’algoritmo evoluto…).
Se un calcolatore svolge 106 operazioni elementari al secondo allora i tempi di attesa sono
| n | n2 | nlog2n |
| 103 | ~1 sec | ~0.01 sec |
| 106 | ~11,5 giorni | ~20 sec |
| 109 | ~30 mila anni | ~8 ore |
| 1010 | ~3 milioni di anni | ~4 giorni |
Se un calcolatore svolgerà, fra qualche anno, 109 operazioni elementari al secondo allora i tempi di attesa saranno
| n | n2 | nlog2n |
| 103 | ~0.001 sec | ~0.00001 sec |
| 106 | ~17 min | ~0.02 sec |
| 109 | ~30 anni | ~30 sec |
| 1010 | ~3000 anni | ~5,5 min |