Comment déterminer l'efficacité d'un algorithme? Il n'y a pas une seule réponse à cette question, car il y a plusieurs aspects de l'efficacité et différents programmes ont besoins de différents aspects.
Une possibilité est de faire tourner une implémentation de celui-ci sur un ordinateur et de mesurer le temps d'exécution. Cette méthode a plusieurs inconvénients. D'abord, le résultat sera valable uniquement pour ce type d'ordinateur, et pour le compilateur utilisé. De plus, la qualité du programmeur peut influencer de manière considérable le résultat.
Une autre possibilité est d'utiliser la complexité asymptotique. Elle permet une comparaison entre deux algorithmes tout en évitant des dépendances sur l'ordinateur, le compilateur et le programmeur. Malheureusement, l'approximation introduite par la complexité asymptotique peut parfois être assez grossière, ce qui risque de fausser le résultat.
La localité est une autre façon d'évaluer l'efficacité d'un algorithme. Elle indique si l'algorithme a tendance à faire un grand nombre d'accès à la mémoire à peu près dans un même intervalle d'adresses, ou si, au contraire, l'algorithme fait des accès dispersés. Une localité importante améliore l'efficacité, car cela fait diminuer les défauts de cache et la pagination
Alors que la complexité asymptotique est souvent indiqué par rapport au cas d'utilisation nécessitant le plus grand temps d'exécution (complexité au pire), il est souvent possible d'avoir une meilleure idée de la complexité si l'on connaît la probabilité des différents cas d'utilisation. Dans ce cas, on peut se prononcer sur la complexité en moyenne qui est souvent plus avantageux que la complexité au pire. Il faut, par contre, faire attention à bien connaître la distribution probabiliste des cas d'utilisation. Il est souvent inacceptable de supposer une distribution uniforme.
Certains algorithmes sont conçu pour un usage particulier. La gestion d'un tampon de texte dans un éditeur de texte, par exemple, peut raisonnablement supposer que les opérations restent localisées dans un petit intervalle du texte, et que la position de cet intervalle change radicalement relativement rarement. Un tel algorithme peut avoir une complexité asymptotique au pire assez catastrophique, alors que le pire des cas n'arrive que très rarement. Même sans utiliser un modèle statistique formel de l'utilisateur, on peut se prononcer de l'efficacité de l'algorithme dans quelques cas typique d'utilisation.