Bij een programma dat grote hoeveelheden gegevens verwerkt: welke verbetering levert waarschijnlijk de grootste versnelling op?

Antwoord: B. Een algoritme met rekencomplexiteit n² vervangen door een algoritme met n log n

Bij n = 1 miljoen gegevens is n² gelijk aan 1 biljoen en n log n ongeveer 20 miljoen, een verschil van een factor 50.000. Vergeleken met het effect van enkele malen door fijne optimalisatie van instructies of hardwareverbeteringen kan een algoritmeverbetering een effect van een andere orde van grootte hebben. Bij prestatieverbetering wordt eerst nagegaan of geen algoritme met hoge rekencomplexiteit wordt gebruikt, waarna verbeteringen als cachegebruik en parallellisatie worden toegevoegd.