Asymptotická složitost: Porovnání verzí

V případě algoritmu [[Rychlé řazení|rychlého řazení]] je časová složitost v nejhorším případě <math>O(N^2)</math> a v průměrném případě <math>O(N\log{N})</math>. Algoritmus násobení čtvercových matic velikosti NxN podle definice má kubickou složitost <math>O(N^3)</math>, tj. problém násobení matic má složitost nejhůř kubickou. [[Strassenův algoritmus]] násobení matic má sožitostsložitost přibližně <math>O(N^{2,89})</math> a jsou známy algoritmy s ještě lepší asymptotickou složitostí. Podobně [[Fourierova transformace#Diskrétní Fourierova transformace|diskrétní Fourierova transformace]] počítaná přímočaře podle definice má složitost <math>O(N^2)</math> a algoritmus [[rychlá Fourierova transformace|rychlé Fourierovy transformace]] má složitost <math>O(N\log{N})</math>.