Per semplificare i calcoli e per rendere più evidente il confronto tra i due algoritmi ipotizziamo che i coefficienti numerici delle funzioni di complessità in tempo siano molto sfavorevoli per la ricerca binaria, per esempio
- Tseq(n) = 5 + 5 * n
- Tbin(n) = 100 + 100 * log2 n
calcoliamo i tempi di attesa al variare di n
| n | Tseq(n) | Tbin(n) | |||
|---|---|---|---|---|---|
| 16 | = 24 | 5+5·16 | = 85 | 100+100·4 | = 500 |
| 64 | = 26 | 5+5·64 | = 325 | 100+100·6 | = 700 |
| 256 | = 28 | 5+5·256 | = 1.285 | 100+100·8 | = 900 |
| 1.024 | = 210 | 5+5·1.024 | = 5.125 | 100+100·10 | = 1.100 |
| 1.048.576 | = 220 | … | > 5.000.000 | 100+100·20 | = 2.100 |
| 1.073.741.824 | = 230 | … | > 5.000.000.000 | 100+100·30 | = 3.100 |
Anche in questa situazione di svantaggio ipotetico l’algoritmo di ricerca binaria si comporta meglio se applicato ad appena 200 elementi!
