Algorithmique et Structures de Données

Parmi les limitations de l’analyse asymptotique on peut citer :

• Les facteurs constants ont de l’importance pour des problèmes de petite taille
• Le tri par insertion est plus rapide que le tri par fusion pour n petit
• Deux algorithmes de même complexité (grand-O) peuvent avoir des propriétés très différentes
• Le tri par insertion est en pratique beaucoup plus efficace que le tri par sélection sur des tableaux presque triés

La complexité en espace peut être étudie de la même manière, avec les mêmes notations. Elle est bornée par la complexité en temps.